只要背後的邏輯不變, 迴圈或遞迴都一樣, 只是喜好選擇
為了用遞迴而刻意去套個不一樣的邏輯才是本末倒置- #include <stdio.h>
- #define MIN(a, b) ((a) < (b) ? (a) : (b))
- #define MAX(a, b) ((a) > (b) ? (a) : (b))
- static int power;
- static int qtyA, qtyB, qtyC;
- static int powA, powB, powC;
- int TestR(int a, int b, int which)
- {
- int min, max, i;
- int powerNeeded;
- switch(which)
- {
- case 0:
- min = (power - qtyB * powB - qtyC * powC) / powA;
- min = MAX(min, 0);
- max = power / powA;
- max = MIN(max, qtyA);
- for (i = min; i <= max; i++)
- {
- if (TestR(i, 0, 1))
- {
- return 1;
- }
- }
- break;
- case 1:
- powerNeeded = power - a * powA;
- min = (powerNeeded - qtyC * powC) / powB;
- min = MAX(min, 0);
- max = powerNeeded / powB;
- max = MIN(max, qtyB);
- for (i = min; i <= max; i++)
- {
- if (TestR(a, i, 2))
- {
- return 1;
- }
- }
- break;
- default:
- powerNeeded = power - a * powA - b * powB;
- if (powerNeeded % powC == 0)
- {
- if (powerNeeded / powC <= qtyC)
- {
- return 1;
- }
- }
- break;
- }
- return 0;
- }
- int TestL()
- {
- int minA = (power - qtyB * powB - qtyC * powC) / powA;
- minA = MAX(minA, 0);
- int maxA = power / powA;
- maxA = MIN(maxA, qtyA);
- int a;
- for (a = minA; a <= maxA; a++)
- {
- int powerNeededB = power - a * powA;
- int minB = (powerNeededB - qtyC * powC) / powB;
- minB = MAX(minB, 0);
- int maxB = powerNeededB / powB;
- maxB = MIN(maxB, qtyB);
- int b;
- for (b = minB; b <= maxB; b++)
- {
- int powerNeededC = powerNeededB - b * powB;
- if (powerNeededC % powC == 0)
- {
- int c = powerNeededC / powC;
- if (c <= qtyC)
- {
- return 1;
- }
- }
- }
- }
- return 0;
- }
- int main()
- {
- int n;
- scanf("%d", &n);
- while(n--)
- {
- int found = 0;
- scanf("%d %d %d %d %d %d %d", &power,
- &qtyA, &qtyB, &qtyC,
- &powA, &powB, &powC);
- found = TestR(0, 0, 0);
- print f("%s\n", found ? "yes" : "no");
- found = TestL();
- print f("%s\n", found ? "yes" : "no");
- }
- return 0;
- }
複製代碼 ...
|