محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی — راهنمای کاربردی

۱۸۲ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۶ دقیقه
محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی — راهنمای کاربردی

در این مطلب، روش نوشتن برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی آموزش داده شده است. در واقع، بازی مفروض است که یک بازیکن می‌تواند ۳، ۵ یا ۱۰ امتیاز در یک حرکت بگیرد. مجموع امتیاز n داده شده است. هدف پیدا کردن تعداد راه‌های رسیدن به امتیاز مشخص شده n، در بازی است. مطالعه مثال زیر برای درک بهتر این مسأله، توصیه می‌شود. شایان ذکر است، پیاده‌سازی روش آموزش داده شده در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است.

997696
Input: n = 20
Output: 4
There are following 4 ways to reach 20
(10, 10)
(5, 5, 10)
(5, 5, 5, 5)
(3, 3, 3, 3, 3, 5)

Input: n = 13
Output: 2
There are following 2 ways to reach 13
(3, 5, 5)
(3, 10)

این مساله در واقع نوعی از مسائل «تبدیل سکه» (Change Making Problem | Coin Changing Problem) است که می‌توان آن را در زمان O(n)‎ و با فضای کمکی O(n)‎ حل کرد.

هدف ساخت جدولی به اندازه n+1 برای ذخیره‌سازی همه امتیازها از ۰ تا n است. برای هر حرکت احتمالی ممکن، (۳، ۵ و ۱۰ امتیازی)، مقادیر در جدول افزایش داده می‌شوند.

برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی در ++C

1// A C++ program to count number of  
2// possible ways to a given score 
3// can be reached in a game where a  
4// move can earn 3 or 5 or 10 
5#include <iostream> 
6using namespace std; 
7  
8// Returns number of ways 
9// to reach score n 
10int count(int n) 
11{ 
12    // table[i] will store count  
13    // of solutions for value i. 
14    int table[n + 1], i; 
15  
16    // Initialize all table 
17    // values as 0 
18    for(int j = 0; j < n + 1; j++) 
19            table[j] = 0; 
20  
21    // Base case (If given value is 0) 
22    table[0] = 1; 
23  
24    // One by one consider given 3 moves  
25    // and update the table[] values after 
26    // the index greater than or equal to  
27    // the value of the picked move 
28    for (i = 3; i <= n; i++) 
29    table[i] += table[i - 3]; 
30      
31    for (i = 5; i <= n; i++) 
32    table[i] += table[i - 5]; 
33      
34    for (i = 10; i <= n; i++) 
35    table[i] += table[i - 10]; 
36  
37    return table[n]; 
38} 
39  
40// Driver Code 
41int main(void) 
42{ 
43    int n = 20; 
44    cout << "Count for " << n  
45         << " is " << count(n) << endl; 
46  
47    n = 13; 
48    cout <<"Count for "<< n<< " is " 
49         << count(n) << endl; 
50    return 0; 
51} 
52  
53// This code is contributed  
54// by Shivi_Aggarwal

برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی در C

1// A C program to count number of possible ways to a given score 
2// can be reached in a game where a move can earn 3 or 5 or 10 
3#include <stdio.h> 
4  
5// Returns number of ways to reach score n 
6int count(int n) 
7{ 
8    // table[i] will store count of solutions for 
9    // value i. 
10    int table[n+1], i; 
11  
12    // Initialize all table values as 0 
13    memset(table, 0, sizeof(table)); 
14  
15    // Base case (If given value is 0) 
16    table[0] = 1; 
17  
18    // One by one consider given 3 moves and update the table[] 
19    // values after the index greater than or equal to the 
20    // value of the picked move 
21    for (i=3; i<=n; i++) 
22       table[i] += table[i-3]; 
23    for (i=5; i<=n; i++) 
24       table[i] += table[i-5]; 
25    for (i=10; i<=n; i++) 
26       table[i] += table[i-10]; 
27  
28    return table[n]; 
29} 
30  
31  
32// Driver program 
33int main(void) 
34{ 
35    int n = 20; 
36    printf("Count for %d is %d\n", n, count(n)); 
37  
38    n = 13; 
39    printf("Count for %d is %d", n, count(n)); 
40    return 0; 
41}

برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی در جاوا

1// Java program to count number of  
2// possible ways to a given score 
3// can be reached in a game where  
4// a move can earn 3 or 5 or 10 
5import java.util.Arrays; 
6  
7class GFG 
8{ 
9    // Returns number of ways to reach score n 
10    static int count(int n) 
11    { 
12        // table[i] will store count of solutions for 
13        // value i. 
14        int table[] = new int[n + 1], i; 
15      
16        // Initialize all table values as 0 
17        Arrays.fill(table, 0); 
18      
19        // Base case (If given value is 0) 
20        table[0] = 1; 
21      
22        // One by one consider given 3  
23        // moves and update the table[] 
24        // values after the index greater  
25        // than or equal to the value of  
26        // the picked move 
27        for (i = 3; i <= n; i++) 
28            table[i] += table[i - 3]; 
29        for (i = 5; i <= n; i++) 
30            table[i] += table[i - 5]; 
31        for (i = 10; i <= n; i++) 
32            table[i] += table[i - 10]; 
33      
34        return table[n]; 
35    } 
36      
37    // Driver code 
38    public static void main (String[] args)  
39    { 
40        int n = 20; 
41        System.out.println("Count for "+n+" is "+count(n)); 
42      
43        n = 13; 
44        System.out.println("Count for "+n+" is "+count(n)); 
45    } 
46} 
47  
48// This code is contributed by Anant Agarwal.

برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی در پایتون ۳

1# Python program to count number of possible ways to a given 
2# score can be reached in a game where a move can earn 3 or 
3# 5 or 10. 
4  
5# Returns number of ways to reach score n. 
6def count(n): 
7  
8    # table[i] will store count of solutions for value i. 
9    # Initialize all table values as 0. 
10    table = [0 for i in range(n+1)] 
11  
12    # Base case (If given value is 0) 
13    table[0] = 1
14  
15    # One by one consider given 3 moves and update the 
16    # table[] values after the index greater than or equal 
17    # to the value of the picked move. 
18    for i in range(3, n+1): 
19        table[i] += table[i-3] 
20    for i in range(5, n+1): 
21        table[i] += table[i-5] 
22    for i in range(10, n+1): 
23        table[i] += table[i-10] 
24  
25    return table[n] 
26  
27# Driver Program 
28n = 20
29print('Count for', n, 'is', count(n)) 
30  
31n = 13
32print('Count for', n, 'is', count(n)) 
33  
34# This code is contributed by Soumen Ghosh 

برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی در #C

1// C# program to count number of  
2// possible ways to a given score 
3// can be reached in a game where  
4// a move can earn 3 or 5 or 10 
5using System; 
6  
7class GFG { 
8      
9    // Returns number of ways to reach  
10    // score n 
11    static int count(int n) 
12    { 
13          
14        // table[i] will store count 
15        // of solutions for value i. 
16        int []table = new int[n + 1]; 
17      
18        // Initialize all table values 
19        // as 0 
20        for(int j = 0; j < n+1; j++) 
21            table[j] = 0; 
22          
23        // Base case (If given value is 0) 
24        table[0] = 1; 
25      
26        // One by one consider given 3  
27        // moves and update the table[] 
28        // values after the index greater  
29        // than or equal to the value of  
30        // the picked move 
31        for (int i = 3; i <= n; i++) 
32            table[i] += table[i - 3]; 
33        for (int i = 5; i <= n; i++) 
34            table[i] += table[i - 5]; 
35        for (int i = 10; i <= n; i++) 
36            table[i] += table[i - 10]; 
37      
38        return table[n]; 
39    } 
40      
41    // Driver code 
42    public static void Main ()  
43    { 
44        int n = 20; 
45        Console.WriteLine("Count for "
46             + n + " is " + count(n)); 
47      
48        n = 13; 
49        Console.Write("Count for "
50            + n + " is " + count(n)); 
51    } 
52} 
53  
54// This code is contributed by nitin mittal.

برنامه محاسبه تعداد راه های رسیدن به امتیاز مشخصی در بازی در PHP

1<?php 
2// PHP program to count number of  
3// possible ways to a given score  
4// can be reached in a game where  
5// a move can earn 3 or 5 or 10  
6// Returns number of ways to reach 
7// score n  
8function counts($n)  
9{  
10    // table[i] will store count  
11    // of solutions for value i.  
12  
13    // Initialize all table  
14    // values as 0  
15    for($j = 0; $j < $n + 1; $j++)  
16            $table[$j] = 0;  
17  
18    // Base case (If given value is 0)  
19    $table[0] = 1;  
20  
21    // One by one consider given 3 moves 
22    // and update the table[] values after 
23    // the index greater than or equal to  
24    // the value of the picked move  
25    for ($i = 3; $i <= $n; $i++)  
26    $table[$i] += $table[$i - 3];  
27      
28    for ($i = 5; $i <= $n; $i++)  
29    $table[$i] += $table[$i - 5];  
30      
31    for ($i = 10; $i <= $n; $i++)  
32    $table[$i] += $table[$i - 10];  
33  
34    return $table[$n];  
35}  
36  
37// Driver Code  
38$n = 20;  
39echo "Count for "; 
40echo($n); 
41echo (" is ");  
42echo counts($n);  
43  
44$n = 13; 
45echo ("\n") ; 
46echo "Count for "; 
47echo($n); 
48echo (" is " );  
49echo counts($n);  
50  
51// This code is contributed  
52// by Shivi_Aggarwal  
53?>

خروجی قطعه کدهای بالا به صورت زیر است.

Count for 20 is 4
Count for 13 is 2

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *