Integer 4 can be expressed as a sum of 1s, 2s, and 3s in seven different ways as follows:
1 + 1 + 1 + 1; (1)
1 + 1 + 2; (2)
1 + 2 + 1; (3)
2 + 1 + 1; (4)
2 + 2; (5)
1 + 3; (6)
3 + 1: (7)
Write a program that determines the number of ways in which a given integer can be expressed as a sum of 1s, 2s, and 3s. You may assume that the integer is positive and less than 20.
Input
The input consists of T test cases. The number of test cases (T ) is given in the first line of the input. Each test case consists of an integer written in a single line.
Output
Print exactly one line for each test case. The line should contain an integer representing the number of ways.
Sample Input
3
4
7
10
Sample Output
7
44
274
Problem Source: SJTU Programming Contest 2004
#include <stdio.h>int sum;void f(int n){ if(n>=3) f(n-3); if(n>=2) f(n-2); if(n>=1) f(n-1); if(n == 0) sum++;}int main(){ int n,num; scanf("%d",&n);
while(n>0) { sum = 0; scanf("%d",&num); f(num); printf("%d/n",sum); n--; }return 0; }
