全文目录
🍕4.3小节——算法初步->递归
问题 A: 吃糖果
问题 B: 数列
问题 C: 神奇的口袋
问题 D: 八皇后
🍕4.3小节——算法初步->递归
地址合集：《算法笔记》4.3小节——算法初步->递归
问题 A: 吃糖果
斐波那契数列的变种题i形，直接写就好了。
#include <cstdio> int F(int n){ if(n == 0 || n == 1) return 1; return F(n - 1) + F(n - 2); } int main(){ int n; while(scanf("%d", &n) != EOF){ printf("%d\n",F(n)); } return 0; }
问题 B: 数列
不能每次都算这个东西，所以利用了非递归的写法，直接存数组了。
#include <cstdio> int F[20]; int main(){ F[0] = 0, F[1] = 1; for(int i = 2;i < 20; i++) F[i] = F[i-1] + F[i-2]; //先打个表0.0 int m,n; if(scanf("%d", &m) != EOF){ while(m--){ if(scanf("%d", &n) == EOF) break; for(int i = 0;i < n;++i){ for(int j = 0;j < n - 1 - i;++j) printf(" "); //输出格式 for(int j = 0;j < 2 * i + 1;++j){ printf("%d",F[j]); if(j != 2 * i ) printf(" "); else printf("\n"); } } } } return 0; }
问题 C: 神奇的口袋
这个其实就是递归的思想，每个元素可以有或者没有，递归出口就是如果所有的都取完了或者大于等于要求的值。
#include <cstdio> int nums[21], n, count, sum;//全局变量用于参数传递 void find(int k){ if(sum == 40) { count++; return; } else if(sum > 40) return; if(k < n){ sum += nums[k];//有这个元素 find(k + 1); sum -= nums[k]; find(k + 1);//无这个元素 } return; } int main(){ while(scanf("%d", &n) != EOF){ for(int i = 0;i < n;++i) scanf("%d", nums + i); count = 0,sum = 0; find(0); printf("%d\n",count); } return 0; }
问题 D: 八皇后
其实本身例题给的就是按照顺序返回的，所以我们用一个数组保存结果，然后直接输出就好了0.0
#include <cstdio> #include <cstring> #include <cmath> int ans[92][8] = {0}, hashTable[9] = {0}, n = 8,ansnum = 0,P[8] = {0}; void generateP(int index){ if(index == n){ memcpy(ans[ansnum++], P, sizeof(P));//最终的结果保存 return; } for(int x = 1; x<= n;x++){ if(hashTable[x] == false){ bool flag = true; for(int pre = 0; pre < index;++pre){ if(abs(index - pre) == abs(x - P[pre])){ flag = false; break; } } if(flag){ //回溯法 P[index] = x; hashTable[x] = true; generateP(index+1); hashTable[x] = false; } } } } int main(){ generateP(0);//打表打表 int m, n; if(scanf("%d", &m) != EOF){ while(m--){ scanf("%d",&n); for(int i = 0;i < 8;++i) printf("%d", ans[n - 1][i]); puts(""); } } return 0; }
