回溯法解整数的划分问题（C语言）

文章目录

• • 回溯法
  • 递归法

回溯法

#include<stdio.h>int nums[100]; //nums用来存放需要放入的数据 int count = 0; //count用来记录一共有多少种划分方法int integerDivide(int cur,int sum,int p,int n){//cur表示当前使用的数组位置 sum表示当前使用位置中所存放的数据之和 p表示当前要划分的数 n表示需要划分的数if(sum > n)return 0;if(sum == n){count++;for (int i = 0; i < cur; i++) { //用来控制输出if (i==cur-1)printf("%d",nums[i]);elseprintf("%d+",nums[i]);}printf("\n");return 0;}for (int i=p;i>0;i--){ //回溯法nums[cur] = i;integerDivide(cur+1,sum+i,i,n);}return count;}int main(){int n,s;printf("请输入你想要划分的正整数n：\n");scanf("%d",&n);s=integerDivide(0,0,n,n);printf("该正整数%d一共有%d种划分方法！\n",n,s);return 0; }

递归法

#include<stdio.h> int Divinteger(int n,int m) {if(n==1||m==1)return 1;else if(n<m)return Divinteger(n,n);else if(n==m)return 1+Divinteger(n,n-1);elsereturn Divinteger(n,m-1)+Divinteger(n-m,m); } int main() {int n,s; //n表示想要划分的整数 s表示该整数划分的种数printf("请输入一个正整数n：\n");scanf("%d",&n);s=Divinteger(n,n);printf("该整数%d一共有%d种划分！\n",n,s);return 0; }

总结

以上是生活随笔为你收集整理的回溯法解整数的划分问题（C语言）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。