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

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

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

// A C++ program to count number of  
// possible ways to a given score 
// can be reached in a game where a  
// move can earn 3 or 5 or 10 
#include <iostream> 
using namespace std; 
  
// Returns number of ways 
// to reach score n 
int count(int n) 
{ 
    // table[i] will store count  
    // of solutions for value i. 
    int table[n + 1], i; 
  
    // Initialize all table 
    // values as 0 
    for(int j = 0; j < n + 1; j++) 
            table[j] = 0; 
  
    // Base case (If given value is 0) 
    table[0] = 1; 
  
    // One by one consider given 3 moves  
    // and update the table[] values after 
    // the index greater than or equal to  
    // the value of the picked move 
    for (i = 3; i <= n; i++) 
    table[i] += table[i - 3]; 
      
    for (i = 5; i <= n; i++) 
    table[i] += table[i - 5]; 
      
    for (i = 10; i <= n; i++) 
    table[i] += table[i - 10]; 
  
    return table[n]; 
} 
  
// Driver Code 
int main(void) 
{ 
    int n = 20; 
    cout << "Count for " << n  
         << " is " << count(n) << endl; 
  
    n = 13; 
    cout <<"Count for "<< n<< " is " 
         << count(n) << endl; 
    return 0; 
} 
  
// This code is contributed  
// by Shivi_Aggarwal

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

// A C program to count number of possible ways to a given score 
// can be reached in a game where a move can earn 3 or 5 or 10 
#include <stdio.h> 
  
// Returns number of ways to reach score n 
int count(int n) 
{ 
    // table[i] will store count of solutions for 
    // value i. 
    int table[n+1], i; 
  
    // Initialize all table values as 0 
    memset(table, 0, sizeof(table)); 
  
    // Base case (If given value is 0) 
    table[0] = 1; 
  
    // One by one consider given 3 moves and update the table[] 
    // values after the index greater than or equal to the 
    // value of the picked move 
    for (i=3; i<=n; i++) 
       table[i] += table[i-3]; 
    for (i=5; i<=n; i++) 
       table[i] += table[i-5]; 
    for (i=10; i<=n; i++) 
       table[i] += table[i-10]; 
  
    return table[n]; 
} 
  
  
// Driver program 
int main(void) 
{ 
    int n = 20; 
    printf("Count for %d is %d\n", n, count(n)); 
  
    n = 13; 
    printf("Count for %d is %d", n, count(n)); 
    return 0; 
}

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

// Java program to count number of  
// possible ways to a given score 
// can be reached in a game where  
// a move can earn 3 or 5 or 10 
import java.util.Arrays; 
  
class GFG 
{ 
    // Returns number of ways to reach score n 
    static int count(int n) 
    { 
        // table[i] will store count of solutions for 
        // value i. 
        int table[] = new int[n + 1], i; 
      
        // Initialize all table values as 0 
        Arrays.fill(table, 0); 
      
        // Base case (If given value is 0) 
        table[0] = 1; 
      
        // One by one consider given 3  
        // moves and update the table[] 
        // values after the index greater  
        // than or equal to the value of  
        // the picked move 
        for (i = 3; i <= n; i++) 
            table[i] += table[i - 3]; 
        for (i = 5; i <= n; i++) 
            table[i] += table[i - 5]; 
        for (i = 10; i <= n; i++) 
            table[i] += table[i - 10]; 
      
        return table[n]; 
    } 
      
    // Driver code 
    public static void main (String[] args)  
    { 
        int n = 20; 
        System.out.println("Count for "+n+" is "+count(n)); 
      
        n = 13; 
        System.out.println("Count for "+n+" is "+count(n)); 
    } 
} 
  
// This code is contributed by Anant Agarwal.

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

# Python program to count number of possible ways to a given 
# score can be reached in a game where a move can earn 3 or 
# 5 or 10. 
  
# Returns number of ways to reach score n. 
def count(n): 
  
    # table[i] will store count of solutions for value i. 
    # Initialize all table values as 0. 
    table = [0 for i in range(n+1)] 
  
    # Base case (If given value is 0) 
    table[0] = 1
  
    # One by one consider given 3 moves and update the 
    # table[] values after the index greater than or equal 
    # to the value of the picked move. 
    for i in range(3, n+1): 
        table[i] += table[i-3] 
    for i in range(5, n+1): 
        table[i] += table[i-5] 
    for i in range(10, n+1): 
        table[i] += table[i-10] 
  
    return table[n] 
  
# Driver Program 
n = 20
print('Count for', n, 'is', count(n)) 
  
n = 13
print('Count for', n, 'is', count(n)) 
  
# This code is contributed by Soumen Ghosh 

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

// C# program to count number of  
// possible ways to a given score 
// can be reached in a game where  
// a move can earn 3 or 5 or 10 
using System; 
  
class GFG { 
      
    // Returns number of ways to reach  
    // score n 
    static int count(int n) 
    { 
          
        // table[i] will store count 
        // of solutions for value i. 
        int []table = new int[n + 1]; 
      
        // Initialize all table values 
        // as 0 
        for(int j = 0; j < n+1; j++) 
            table[j] = 0; 
          
        // Base case (If given value is 0) 
        table[0] = 1; 
      
        // One by one consider given 3  
        // moves and update the table[] 
        // values after the index greater  
        // than or equal to the value of  
        // the picked move 
        for (int i = 3; i <= n; i++) 
            table[i] += table[i - 3]; 
        for (int i = 5; i <= n; i++) 
            table[i] += table[i - 5]; 
        for (int i = 10; i <= n; i++) 
            table[i] += table[i - 10]; 
      
        return table[n]; 
    } 
      
    // Driver code 
    public static void Main ()  
    { 
        int n = 20; 
        Console.WriteLine("Count for "
             + n + " is " + count(n)); 
      
        n = 13; 
        Console.Write("Count for "
            + n + " is " + count(n)); 
    } 
} 
  
// This code is contributed by nitin mittal.

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

<?php 
// PHP program to count number of  
// possible ways to a given score  
// can be reached in a game where  
// a move can earn 3 or 5 or 10  
// Returns number of ways to reach 
// score n  
function counts($n)  
{  
    // table[i] will store count  
    // of solutions for value i.  
  
    // Initialize all table  
    // values as 0  
    for($j = 0; $j < $n + 1; $j++)  
            $table[$j] = 0;  
  
    // Base case (If given value is 0)  
    $table[0] = 1;  
  
    // One by one consider given 3 moves 
    // and update the table[] values after 
    // the index greater than or equal to  
    // the value of the picked move  
    for ($i = 3; $i <= $n; $i++)  
    $table[$i] += $table[$i - 3];  
      
    for ($i = 5; $i <= $n; $i++)  
    $table[$i] += $table[$i - 5];  
      
    for ($i = 10; $i <= $n; $i++)  
    $table[$i] += $table[$i - 10];  
  
    return $table[$n];  
}  
  
// Driver Code  
$n = 20;  
echo "Count for "; 
echo($n); 
echo (" is ");  
echo counts($n);  
  
$n = 13; 
echo ("\n") ; 
echo "Count for "; 
echo($n); 
echo (" is " );  
echo counts($n);  
  
// This code is contributed  
// by Shivi_Aggarwal  
?>

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

Count for 20 is 4
Count for 13 is 2

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

• مجموعه آموزش‌های برنامه‌نویسی پایتون
• آموزش تکمیلی برنامه‌نویسی پایتون
• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
• آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس