编程题一道
输出和为一个给定整数的所有组合
例如n=5
5=1+4；5=2+3（相加的数不能重复）
则输出
1，4；2，3
[解决办法]
int main(int argc, char* argv[])
{
int iNum = 0;
printf( "Please Input the number: ");
scanf( "%d ", &iNum);
int iTemp = iNum/2 + 1;
for (int i = 0; i < iTemp; i++)
{
printf( "%d,%d\n ", i, iNum-i);
}
return 0;
}
[解决办法]
6=1+5, 2+4, 1+2+3 ?
[解决办法]
#include <iostream>
using namespace std;
int sum=0;
int Num(int n,int a)
{
sum+=n;
if(n==0)
{
cout < <endl;
return 0;
}
else
{
if(sum> a)
{
sum-=n;
n-=1;
return Num(n,a);
}
else
{
cout < < "+ " < <n;
return Num(n,a);
}
}
}
int main()
{
int a=0,n=0,summ=0;
cin> > a; //输入的数
for(int i=a;i> 0;i--)
{
n=a-i; //取出减去i后的得数
if(n> =i) //当n> =i(即3=3时)n最高只能是i,以免出现6=2+4的重复现象
{
n=i;
}
cout < <a < < "= " < <i;
if(n==0)
{
cout < <endl;
}
sum=i;
while(n> 0) //n==0进行下一次取n操作
{
summ+=1;
Num(n,a); //对n进行分解
if(n!=1)
{
cout < <a < < "= " < <i;
}
sum=i; //为进行下一步处理,使sum清0
if(sum+n+1 <a && i!=1 && n!=1)//为适应出现6=2+2+1+1情况使6=2+2+2中的第3个2划分
{
cout < < "+ " < <n;
sum+=n;
n-=1;
Num(n,a);
sum=i;
cout < <a < < "= " < <i;
summ+=1;
}
else
{
n-=1;
}
}
}
summ+=1;
cout < < "num = " < <summ < <endl;
return 0;
}
看看对不哦
[解决办法]
回溯法
[解决办法]
貌似很容易,先算最大的加数个数,sum=1+2+3+4等等,直到输入数inputn-sum <n,这样n就是最大的加数个数,再使每个加数按升序排列,穷举就ok了.(当然,小于n个加数的也要算)
[解决办法]
我用递归写的，不会输出重复的数。
#include <stdio.h>
int nums[10000];
int count=0;
void Print()
{
int i;
for (i=0; i <count-1; ++i) printf( "%d, ",nums[i]);
printf( "%d; ", nums[i]);
}
void Cal(int sum, int min, int first)
{
int i;
for (i=min; sum-i> i; ++i)
{
nums[count++]=i;
Cal(sum-i, i+1, 0);
--count;
}
if (first) return;
nums[count++]=sum;
Print();
--count;
}
int main()
{
int sum;
scanf( "%d ", &sum);
Cal(sum, 1, 1);
}
[解决办法]
c#版递归实现,m为给定整数,测试通过。
private int[] temp=new int[m]; int curPos=0;
private void Find(int CurVal)
{
temp[curPos] = CurVal;
int Sum = 0;
for (int lint_LoopCount = 0; lint_LoopCount <= curPos; lint_LoopCount++)
{
Sum += this.temp[lint_LoopCount];
}
if (Sum == m&&curPos!=0)
{
string lstg_Temp = " ";
for (int lint_LoopCount = 0; lint_LoopCount <= curPos; lint_LoopCount++)
{
lstg_Temp += temp[lint_LoopCount] + ", ";
}
MessageBox.Show(lstg_Temp);
curPos--;
return;
}
else if (Sum > m) { curPos--; return; }
else
{
for (int i = CurVal + 1; i < m; i++)
{
curPos++;
Find(i);
}
curPos--;
}
}
调用函数：
for (int i = 1; i < m i++)
{
this.curPos = 0;
this.Find(i);
}
