Question

C++问题（统计和的个数)

输入五个整数（总和不大于10000），任其中1个或多个相加，问可得多少个不同的数字？
请高手指点下，用什么思路来做这道题？

Answer 1

这是我写的代码，用向量vector和数组来实现，说明都注释在代码中了，希望对你有帮助噢：）

#include<iostream>
#include<vector> // 使用vector向量
using namespace std;

#define MAXSUM 10000 // 把最大的和10000设为常量

void getSum(); // 定义一个函数，用于完成此算法
int main()
{
getSum();
return 0;
}

void getSum()
{
int arr[5];
vector<int> bufSum; // 定义2个int型向量
vector<int> totalSum;
int sum;
do // 让使用者输入5个整数，并判断和是否大于10000，若是，请重新输入
{
sum = 0;
cout << "请输入5个整数（和不超过10000）" << endl;
for(int i = 0; i < 5; i++)
{
cin >> arr[i];
sum += arr[i];
}
}
while(sum > MAXSUM);

for(int i = 0; i < 4; i++) // 将5个整数中2个数相加，并用vector中的函数push_back()将和放入向量bufSum中。
{
for(int j = i + 1; j < 5; j++)
{
bufSum.push_back(arr[i] + arr[j]);
}
}

for(int i = 0; i < 5; i++) // 将5个整数中3个数相加，并用vector中的函数push_back()将和放入向量bufSum中。
{
for(int j = 0; j < 5; j++)
{
for(int k = 0; k < 5; k++)
{
if(i == j || i == k || j == k) // 如果i, j, k任意两两相等，则这一步循环什么也不做(continue)。
{
continue;
}
bufSum.push_back(arr[i] + arr[j] + arr[k]);
}
}
}

for(int i = 0; i < 5; i++) // 将5个整数中4个数相加，并用vector中的函数push_back()将和放入向量bufSum中。
{
for(int j = 0; j < 5; j++)
{
for(int k = 0; k < 5; k++)
{
for(int w = 0; w < 5; w++)
{
if(i == j || i == k || i == w || j == k || j == w || k == w) // 如果i, j, k, w任意两两相等，则这一步循环什么也不做(continue)。
{
continue;
}
bufSum.push_back(arr[i] + arr[j] + arr[k] + arr[w]);
}
}
}
}

bufSum.push_back(sum); // sum是这5个整数的和，在输入时已算出，且sum定义在getSum()函数中，
//variable scope为整个getSum()函数体，用完不释放，故可以继续使用

for(int i = 1; i < bufSum.size(); i++) // 判断向量bufSum中有无相等的和，若有，则将后面这个与前相等的和设为（MAXSUM + 1）
// 因为有效的和不会超过MAXSUM
{
for(int j = 0; j < i; j++)
{
if(bufSum[j] == bufSum[i])
{
bufSum[i] = (MAXSUM + 1);
}
}
}

int count = 0;
for(int i = 0; i < bufSum.size(); i++) // 把所有有效的和从向量bufSum存入向量totalSum中，并将count加1
{
if(bufSum[i] <= MAXSUM)
{
totalSum.push_back(bufSum[i]);
count++;
}
}
// 此时得到的向量totalSum的元素就是所有有效的和

cout << "总共有" << count << "个可能的和" << endl << "所有可能的和为：" << endl;
for(int i = 0; i < totalSum.size(); i++)
{
cout << totalSum[i];
cout << endl;
}
}

Answer 2

嵌套循环或者回溯。
反正只有5个整数，嵌套5个循环问题不大。
用回溯代码会短很多。我给一个回溯的。
#include<iostream>

using namespace std;

int stack[10000]; //用来存储不同的和的栈
int top = 0; //栈顶

void Fun(const int a[], int max, int n, int & s);
void Insert(int s);

int main()
{
const int MAX = 5;
int a[MAX] = {0};
for (int i=0; i<MAX; i++)
cin >> a[i];
for (int i=0; i<MAX; i++)
cout << a[i] << " ";
cout << endl;

int s = 0;
Fun(a, MAX, 0, s);
cout << top << endl;

system("pause");
return 0;
}

void Fun(const int a[], int max, int n, int & s)
{
if (n == max)
{
//cout << s << " ";
Insert(s);
}
else
{
Fun(a, max, n+1, s); //第一次不加a[n]
s += a[n];
Fun(a, max, n+1, s);//第二次加a[n]
s -= a[n]; //还原
}
}

//按增序插入数组
void Insert(int s)
{
int mid, left = 0, right = top -1;

if (top == 0 || s > stack[right]) //最大
{
stack[top++] = s;
return;
}
else if (s < stack[left]) //最小
{
for (int i=right; i>=0; i--)
{
stack[i+1] = stack[i];
}
stack[0] = s;
top++;
return;
}
while (left <= right)
{
mid = (left + right) / 2;
if (stack[mid] == s)//相等则什么也不做
return ;
if (stack[mid] < s)
{
left = mid + 1;
}
else if (stack[mid] > s)
{
right = mid - 1;
}
}
if (stack[mid] < s)
mid++;
//插入到a[mid]之前
for (int i=top-1; i>=mid; i--)
{
stack[i+1] = stack[i];
}
stack[mid] = s;
top++;
}

Answer 3

先定义5个数，用户输入后判断是否《10000 然后用循环，使任意两个相加，3个相加，4个相加，判断他们的结果是否相等不等的话N+1 最后n就是结果数

Answer 4

用循环
for (i=0;i<5;i++)
for (j=i;j<5;j++)
{
s++;
}
0--->0,1,2,3,4
1--->1,2,3,4
2--->2,3,4
3--->3,4
4--->4