金山笔试题！！
题目是这样的：
任一给4个正整数，求出它的所有加和的总数。并按相应的格式打印出来
如：1，2，3，4
共有加和数10种。
结果打印如下：
和为1有1种
1＝1；
和为2有1种
2＝2；
...
和为6有2种
6＝1+2+3；
6＝2+4；
...
和为10有1种
10＝1+2+3+4；
问题点数：20、回复次数：31Top
1 楼yeehya（老汉了）回复于 2004-11-06 14:42:00 得分 0
怎么没人答吗?我帮顶~Top
2 楼yeehya（老汉了）回复于 2004-11-06 14:43:26 得分 0
看着简单,写出来好象很烦人.
有没有简单明了的解答.等待...
Top
3 楼wxu2（蓝鸟）回复于 2004-11-06 15:16:43 得分 0
这么简单的题目是金山出的？
Top
4 楼yeehya（老汉了）回复于 2004-11-06 15:55:04 得分 0
请写出来.谢谢...Top
5 楼chinayang9（中国杨）回复于 2004-11-06 15:59:55 得分 0
要不要求时间复杂度啊?
如果不要求的话,从大数开始往小数加就是了~
可以用递归函数来实现
每次把num-N*4传给下一个递归函数做为输入值.Top
6 楼wzq1979（一无所有）回复于 2004-11-06 16:12:29 得分 0
可以转化为组合的问题。Top
7 楼allenchou（洪）回复于 2004-11-06 16:28:58 得分 5
先按升序排序;
然后求出和：Total = a[0] + a[1] + a[2] + a[3]
然后：
for(int sum = a[0]; sum <= Total; sum++)
{
int nCount = 0;
for(int i=0; i< 4;i++) {
int temp = a[i];
if(temp == sum){
nCount++;
cout << sum << "=" << a[i] << endl;
}
for(int j = i+1;j<4;j++) {
int temp = a[i] + a[j];
if(temp == sum) {
nCount++;
cout << sum << "=" << a[i] << "+" << a[j] << endl;
}
for(int k = j+1;k<4;k++) {
int temp = a[i] + a[j]+a[k];
if(temp == sum) {
nCount++;
cout << sum << "=" << a[i] << "+" << a[j]<<"+"<<a[k] << endl;
}
for(int l =k+1;l<4;l++) {
int temp = a[i] + a[j] + a[k] + a[l];
if(temp == sum) {
nCount++;
cout << sum << "=" << a[i] << "+" << a[j]<<"+"<<a[k]<<"+"<<a[l]<< endl;
}
}
}
}
}
if(nCount != 0) {
cout << "等于" << sum << "有" << nCount <<"种:" << endl;
}
nCount = 0;
}
简单的测了一下，可以的，不过还没有考虑输入相同变量的情况！
Top
8 楼HJ_34（刺桐游子）回复于 2004-11-06 16:31:25 得分 0
用个数组作为接收值，
然后用双层嵌套成不？
chinayang9(中国杨)：如何理解时间复杂度啊？能否给小弟指点一二。Top
9 楼allenchou（洪）回复于 2004-11-06 16:31:33 得分 0
这个程序很简单，只有4个数，可以解决问题，但可能不是最优的算法，大家载想想优化的吧！Top
10 楼zhouqingyuan（浪帆）回复于 2004-11-06 16:39:12 得分 5
已知只有4个数，所以settype[][]直接设置了，如果可能有多个数的话，则可以先求出所有的子集存在settype数组中（更简单的是用vector<vector<int> >来存贮这些子集合以代替settype[][]数组。
#include <vector>
#include <iostream>
using namespace std;
struct StructSumType
{
int sum;
vector<vector<int> > sumtypevec;
};
int Find(int sum,vector<StructSumType> SumType)
{
for(int i=0;i<SumType.size();i++)
{
if(SumType[i].sum==sum)
{
return i;
}
}
return -1;
}
int main()
{
int a[5]={0};
cout<<"请输入4个正整数:"<<endl;
int a0;
for(int count=0;count<4;count++)
{
cin>>a0;
a[count]=a0;
}
int settype[15][4]={{0,4,4,4},{1,4,4,4},{2,4,4,4},{3,4,4,4},
{0,1,4,4},{0,2,4,4},{0,3,4,4},{1,2,4,4},{1,3,4,4},{2,3,4,4},
{0,1,2,4},{0,1,3,4},{0,2,3,4},{1,2,3,4},{0,1,2,3}};
vector<StructSumType> SumType;
for(int i=0;i<15;i++)
{
int sum=a[settype[i][0]]+a[settype[i][1]]+a[settype[i][2]]+a[settype[i][3]];
vector<int> intVec;
for(int j=0;j<4;j++)
{
if(settype[i][j]!=4)
{
intVec.push_back(a[settype[i][j]]);
}
}
int index=Find(sum,SumType);
if(index==-1)
{
StructSumType structsumtype;
structsumtype.sum=sum;
structsumtype.sumtypevec.push_back(intVec);
SumType.push_back(structsumtype);
}
else
{
SumType[index].sumtypevec.push_back(intVec);
}
}
for(int m=0;m<SumType.size();m++)
{
cout<<"和为"<<SumType[m].sum<<"的情况有"<<SumType[m].sumtypevec.size()<<"种"<<endl;
for(int n=0;n<SumType[m].sumtypevec.size();n++)
{
cout<<SumType[m].sum<<"=";
for(int n0=0;n0<SumType[m].sumtypevec[n].size()-1;n0++)
{
cout<<SumType[m].sumtypevec[n][n0]<<"+";
}
cout<<SumType[m].sumtypevec[n][SumType[m].sumtypevec[n].size()-1]<<endl;
}
}
return 0;
}Top
11 楼allenchou（洪）回复于 2004-11-06 16:47:29 得分 0
楼上，这是一个算法题，是不能用存储的！Top
12 楼zhouqingyuan（浪帆）回复于 2004-11-06 16:54:14 得分 0
不能用存储？？什么意思？Top
13 楼h77（大山猫）回复于 2004-11-06 22:07:18 得分 0
在这几个数中,最大的和为这几个数的累加即10
那么它的所有的和一定是1-10
用几个循环分别判断哪几个数相加能得到1-10中的每一个数就行了Top
14 楼stone1982（强）回复于 2004-11-06 22:57:45 得分 0
我想了一个方法，大家看看
利用组合的思想，求出4个数中依次选4，3，2，1 个数的组合情况，求得一个解之后，计算这组数
的和数，零时存起来，最后对和数进行排序，并输出相应的组合数。完了。Top
15 楼hustacsky（见好不收）回复于 2004-11-07 11:01:22 得分 0
我开始也是这样想的，不过你只能打印和，而打印组合数 ，而且要一起打印就比较麻烦了Top
16 楼hustacsky（见好不收）回复于 2004-11-07 11:06:12 得分 0
比如：和为6有2种
6＝1+2+3；
6＝2+4；每次检测到和为6的时候就要存起来 ，直到没有和为6 的组合再把这个数组打印出来
如果数多起来的话，那不是要 用很多很多数组来存组合数 ，疑惑中，望高手指点好的方法！！Top
17 楼milozy1983（Detective）回复于 2004-11-07 13:45:19 得分 5
/*
Name : 算法小练习
Auther: 跳蚤侦探
*/
int Num[4]; /* 输入的四个数 */
int Resoult[15]; /* C(1,4) + C(2,4) + C(3,4) + C(4,4)最多15种组合结果 */
int total=0; /* 一共有几种结果 */
void Input(); /* 输入 */
void End(); /* 结束 */
void PrintNum();
void SortNum(); /* 对输入的四个数排序 */
void Stat(int point,int sum,int curr_count,int count); /* 统计一共有几种组合结果 */
/* 显示每种结果的组合情况 */
void combin(int point,int sum,int target,int array[],int pot);
main()
{int count,point,array[4];
Input();
SortNum();
for(count=1;count<=4;count++) /* 递归寻找所有组合结果 */
for(point=0;point<=4-count;point++)
Stat(point,0,0,count);
for(count=0;count<total;count++) { /* 显示结果 */
printf("way of %d\n",Resoult[count]);
for(point=0;point<=3;point++)
combin(point,0,Resoult[count],array,0);
}
End();
}
void combin(int point,int sum,int target,int array[],int pot)
{int i;
if(point==4)
return;
sum=sum+Num[point];
array[pot]=Num[point];
pot++;
if(sum>target)
return;
else if(sum==target) { /*显示结果*/
for(i=0;i<pot;i++)
printf("%d ",array[i]);
printf("\n");
}
else
for(i=point+1;i<4;i++)
combin(i,sum,target,array,pot);
}
void Stat(int point,int sum,int curr_count,int count)
{int i;
if(point==4)
return;
sum=sum+Num[point];
curr_count++;
if(curr_count != count) { /* 继续递归累加 */
for(i = point+1 ;i < 4; i++)
Stat(i,sum,curr_count,count);
}
else { /* 判断是否添加新的可能结果 */
if(total==0) {
Resoult[total]=sum;
total++;
}
else {
for(i=0;i<total;i++)
if(Resoult[i]==sum)
break;
if(i>=total) {
Resoult[total]=sum;
total++;
}
}
}
}
void Input()
{
int i;
for(i = 0;i < 4;i++)
scanf("%d" , &Num[i]);
}
void SortNum()
{
int i,j,t;
for(i = 0;i < 3;i++)
for(j = i+1;j < 4;j++)
if(Num[j] < Num[i]) {
t = Num[i];
Num[i] = Num[j];
Num[j] = t;
}
}
void End()
{
getch();
}Top
18 楼milozy1983（Detective）回复于 2004-11-07 13:47:47 得分 0
我的程序是用win-tc编译通过的，主要思想是4个数最多能组合成15种结果，所以先求出4个数总共能组合的结果可能。然后再用分别求出每种结果的各种组合情况，如有问题请指教，因为我也是刚才看了刚才做的。Top
19 楼lanphaday（恋花蝶）回复于 2004-11-07 17:14:53 得分 0
markTop
20 楼Kenny_Glacier（冰坼）回复于 2004-11-07 17:54:01 得分 0
markTop
21 楼fqj2004（amor）回复于 2004-11-07 18:33:11 得分 0
mark
Top
22 楼sukaru（逍遥子）回复于 2004-11-08 11:11:44 得分 0
强啊，我写了一个晚上，楞是没写出来的Top
23 楼monk2000（老实和尚）回复于 2004-11-08 13:05:38 得分 0
回复人： h77(大山猫) ( ) 信誉：100 2004-11-06 22:07:00 得分: 0
在这几个数中,最大的和为这几个数的累加即10
那么它的所有的和一定是1-10
用几个循环分别判断哪几个数相加能得到1-10中的每一个数就行了
=================================================================
这种方法不行吧，只能对于1、2、3、4啊
我觉得要用组合，必须把结果存储起来，以便以后判断。Top
24 楼Mag1cD（Meditator）回复于 2004-11-08 13:50:06 得分 0
reTop
25 楼snowboy1124（雪夜獨行）回复于 2004-11-08 13:57:55 得分 0
使用回溯或者递归求解出这几个数的所有组合 ， 将求解的组合里的数字相加，得到值Top
26 楼wangjie__（望天）回复于 2004-11-08 15:11:19 得分 5
给个简单的算法：vc6.0下通过，可以运行一下哦！
#include <stdio.h>
#define ARRAY_SIZE 4
#define MAX_NUM (1<<ARRAY_SIZE)
int main(void)
{
int h,i, j;
int sum;
int a[ARRAY_SIZE] = {1,2,3,4};
int count = 0;
for(h=1;h<=10;h++)
{
for(i = 0; i < MAX_NUM; i++)
{
sum = 0;
for(j = 0; j < ARRAY_SIZE; j++)
{
if(i & (1 << j))
sum += a[j];
}
if(h == sum)
{
printf("%d: ", ++count);
for(j = 0; j < ARRAY_SIZE; j++)
{
if(i & (1 << j))
printf("%d + ", a[j]);
}
printf("\b\b= %d.\n",h);
}
}
}
printf("\nTotal: %d.\n", count);
return 0;
}Top
27 楼mengxiangfeng（寒江雪）回复于 2004-11-08 15:27:10 得分 0
写的可以Top
28 楼tw829（唐牛）回复于 2004-11-08 15:28:53 得分 0
markTop
29 楼hustacsky（见好不收）回复于 2004-11-10 09:35:18 得分 0
谢谢大家的支持！！！Top
30 楼lovedna（有间道）回复于 2005-03-21 01:01:30 得分 0
wangjie__(望天) 写的太拉圾了Top
31 楼lovedna（有间道）回复于 2005-03-21 01:06:20 得分 0
wangjie__(望天) 写得没有一点用的CODE
Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
