Question

一个计算的程序问题

要求：从1～33中间选6个数字相加，和为 x （x由用户输入），按数字大小降序列出所有

结果，还要求可以用户选出其中的n个数字，列出结果，
例如：x＝23 ，则输出 8，5，4，3，2，1
7，6，4，3，2，1
若用户要求6个数中一个为6，则输出7，6，4，3，2，1

若用户要求6个数中一个为1，则输出7，6，4，3，2，1
8，5，4，3，2，1

若用户要求6个数中一个为8，则输出8，5，4，3，2，1

若用户要求6个数中同时存在8，1则输出8，5，4，3，2，1

若用户要求6个数中同时存在4，3则输出7，6，4，3，2，1
8，5，4，3，2，1
这样一个程序怎么设计啊?输出的结果最好能以文件形式保存，x是几文件名就是什么
希望大家够及时给出解决方案
其实就是一个算彩票的

Answer 1

看了下你的题目觉得有意思，就写了个，功能被我扩展了一点，不过写的有点糟糕，其实还有N多不完善的地方，比如存结果的数组大小要在编译期间确定，使用链表或者动态调整数组的话也没什么难的，不过确凭空增加了代码的复杂度，还有查找所有满足时使用的是递归并且那个函数参数有点多所以范围大一点可能导致栈溢出，所以暂时写成这样了，有什么不懂的话可以发消息给我：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int Prepare(int sum, int n)
{
--n;
int i = n * (1 + n) / 2;
return sum - i;
}

int NoDummy(int* beg, int* end, int dummy)
{
while(beg != end)
if(*beg++ == dummy)
return 0;
return 1;
}

int NoDupNum(int* beg, int* end)
{
int* p;
for(; beg != end; ++beg)
for(p = beg + 1; p != end; ++p)
if(*p == *beg)
return 0;
return 1;
}

int NoDupSeq(int** beg, int** end, int* p, int n)
{
while(*beg && (beg != end))
{
if(memcmp(*beg, p, sizeof(int) * n) == 0)
return 0;
++beg;
}
return 1;
}

inline int Cmp(const void* lhs, const void* rhs)
{
return *(const int*)rhs - *(const int*)lhs;
}

void FindAllMatch(int sum, int baseNum, int nextNum, int cn, int n, int* pn, int* beg, int* end, int** outBeg, int** outEnd, int dummy)
{
int i, *tmp, **nullPos;

for(i = nextNum; i >= baseNum; --i)
{
if(*pn > n)
{
for(tmp = end - (*pn - n); tmp != end; ++tmp)
*tmp = dummy;
}
*pn = n;
*(end - n) = i;

if(sum - i == 0 && NoDummy(beg, end, dummy) && NoDupNum(beg, end))
{
tmp = (int*)malloc(sizeof(int) * cn);
memcpy(tmp, beg, sizeof(int) * cn);
qsort(tmp, cn, sizeof(int), Cmp);
if(NoDupSeq(outBeg, outEnd, tmp, cn))
{
nullPos = outBeg;
while(*nullPos && nullPos != outEnd)
++nullPos;
if(nullPos == outEnd)
{
puts("Number of results bigger than the size of result array.");
exit(1);
}
*nullPos = tmp;
}
else
free(tmp);
}
if(sum - i > 0 && n - 1 > 0)
FindAllMatch(sum - i, baseNum, sum - i, cn, n - 1, pn, beg, end, outBeg, outEnd, dummy);
}
}

void GetResult(int lb, int ub, int n, int goal, int** resBeg, int** resEnd)
{
assert(lb < ub);

int* tmp = (int*)malloc(sizeof(int) * n);
int dummy = ub + 1;
int nextNum = goal < ub ? Prepare(goal, n) : ub;
int fn = n;

FindAllMatch(goal, lb, nextNum, n, n, &fn, tmp, tmp + n, resBeg, resEnd, dummy);
free(tmp);
}

int Contains(int* beg, int* end, int* subBeg, int* subEnd)
{
int* p;
for(; subBeg != subEnd; ++subBeg)
{
for(p = beg; p != end; ++p)
{
if(*p == *subBeg)
break;
}
if(p == end)
return 0;
}
return 1;
}

void SearchForSuit(int n, int** resBeg, int** resEnd, int* beg, int* end, FILE* output)
{
int** p, *x;
for(p = resBeg; *p && p != resEnd; ++p)
{
if(Contains(*p, *p + n, beg, end))
{
for(x = *p; x != *p + n; ++x)
fprintf(output, "%d ", *x);
putc('\n', output);
}
}
}

void CleanUpMemory(int** resBeg, int** resEnd)
{
int** p = resBeg;
while(*p && p != resEnd)
free(*p++);
}

#define RES_ARRAY_SIZE 500 // 结果数组大小，不够的话自己调大点

int main()
{
int goal = 23; // 数字和
int n = 6; // 由6个数字相加得
int lb = 1, ub = 33; // 范围
int a[] = {4, 3}; // 其中包含4, 3

// 存所有满足条件的结果
int *resBeg[RES_ARRAY_SIZE] = {0};
int ** resEnd = resBeg + RES_ARRAY_SIZE;

// 范围1~33, 6个数字的和为23, 结果存在resBeg数组里
GetResult(lb, ub, n, goal, resBeg, resEnd);

// 筛选出有4, 3两个数的序列，打印到stdout, 你可以把它改成一个文件指针
SearchForSuit(n, resBeg, resEnd, a, a + sizeof(a) / sizeof(a[0]), stdout);

// 整理内存
CleanUpMemory(resBeg, resEnd);

return 0;
}

方法二：

用今天自己找出的求组合的方法，优化一下，效率有所提高(排除了去重等过程)：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Print(int* beg, int* end)
{
while(beg != end)
printf("%d ", *beg++);
putchar('\n');
}

inline int Prepare(int goal, int n)
{
return goal - (n - 1) * n / 2;
}

typedef unsigned long long ull;

// count for combinations
ull CC(ull n, ull r)
{
ull Anr = 1;
ull Arr = 1;

for(; r > 0; Anr *= n--, Arr *= r--);

return Anr / Arr;
}

int Sum(int* beg, int* end)
{
int sum = 0;
while(beg != end)
sum += *beg++;
return sum;
}

// 求组合序列的函数
int** C(int n, int m, int** resBeg, int** resEnd, int goal)
{
int i;
int *p, *x, *trace_back, **nullPos;

p = (int*)malloc(sizeof(int) * m);

for(i = 1; i <= m; ++i)
p[i - 1] = i;

trace_back = p + m - 1;

if(m != n)
do{
if(Sum(p, p + m) == goal)
memcpy(*resBeg++, p, sizeof(int) * m);
if(*trace_back < n)
++*trace_back;
else
{
while(*trace_back - *(trace_back - 1) <= 1)
--trace_back;
--trace_back;
++*trace_back;
for(x = trace_back + 1; x != p + m; ++x)
*x = *(x - 1) + 1;
trace_back = p + m - 1;
}
}while(*p != n - m + 1);

if(Sum(p, p + m) == goal)
memcpy(*resBeg++, p, sizeof(int) * m);

nullPos = resBeg;
while(nullPos != resEnd)
{
free(*nullPos);
*nullPos++ = 0;
}
free(p);

return resBeg;
}

int Contains(int* beg, int* end, int* subBeg, int* subEnd)
{
int* p;

if(subEnd - subBeg > end - beg)
{
puts("Range error!");
return 0;
}

for(; subBeg != subEnd; ++subBeg)
{
for(p = beg; p != end; ++p)
if(*subBeg == *p)
break;
if(p == end)
return 0;
}
return 1;
}

void SearchForSuit(int goal, int n, int* beg, int* end)
{
int m = Prepare(goal, n);
int** res, **resEnd, **p;
ull cc;

if(m < n)
{
puts("No solution!");
return;
}

cc = CC(m, n);

res = (int**)malloc(sizeof(int*) * cc);
for(p = res; p != res + cc; ++p)
*p = (int*)malloc(sizeof(int) * n);

resEnd = C(m, n, res, res + cc, goal);

if(resEnd == res)
puts("No solution!");
else
{
for(p = res; p != resEnd; ++p)
if(Contains(*p, *p + n, beg, end))
Print(*p, *p + n);

for(p = res; p != resEnd; ++p)
free(*p);
}
free(res);
}

int main()
{
int elems[] = {2, 3};
SearchForSuit(23, 6, elems, elems + 2);
return 0;
}

PS: 不知道我这些方法叫不叫"全真模拟选号"...

Answer 2

刚刚路过.如果楼主加到100分,偶做个程序可完全符合你要求.

还有指出一点:符合要求的排列可能有限,但不借助数学分析方法而全真模拟选号再筛出所要号,程序要经过很大的运算量.

"全真模拟选号"...............总觉得这问题是彩票程序的......也可能不是?呵呵呵.还有三天了.楼主莫不要等最后一天才现身??

看来楼主现身，不好不写了，然电脑有毛病，没法调试，干写了个先，有空再改，给不给分无所谓。

..................

调好了.输入形式如下:

比如想要和为23,且想一同显示带4和6的数组,则在程序提示下依次输入: 23(回车)

4,6(回车)(不想忘记豆号).

产生的文件在C盘上找.(我的编译器好象坏了,产生的文件不是TXT的??)

#include"stdio.h"
#include"stdlib.h"
void main()
{

FILE *fp;
int a[6]={0,0,0,0,0,0},ge,shi,bai;
int b[500][6];
char na[]="c:\\000",ch,kj,*opp,ms[1];
int j,jj,yao1,yao,sum,k,kk=0;
printf("please input the sum : ");
scanf("%d",&sum);
ge=sum%10;
shi=(sum%100-ge)/10;
bai=(sum-shi*10-ge)/100;
itoa(bai,ms,10);
na[3]=ms[0];
itoa(shi,ms,10);
na[4]=ms[0];
itoa(ge,ms,10);
na[5]=ms[0];
opp=na;
printf("the number to lock( as xx,xx) : ");
fflush(stdin);
scanf("%d,%d",&yao,&yao1);

if((fp=fopen(opp,"wt+"))==NULL)
{
printf("Cannot open file strike any key exit!");
getch();
exit(0);
}
fflush(stdin);
for (a[0]=1;a[0]*6+15<=sum;a[0]++){
for (a[1]=a[0]+1;a[0]+a[1]*5+10<=sum;a[1]++){
for (a[2]=a[1]+1;a[0]+a[1]+a[2]*4+6<=sum;a[2]++){
for (a[3]=a[2]+1;a[0]+a[1]+a[2]+a[3]*3+3<=sum;a[3]++){
for (a[4]=a[3]+1;a[0]+a[1]+a[2]+a[3]+a[4]*2+1<=sum;a[4]++){
for (a[5]=a[4]+1;a[5]<=sum-21+6;a[5]++){
if (a[0]+a[1]+a[2]+a[3]+a[4]+a[5]==sum) {
for (k=5;k>=0;k--) {
if (a[k]==yao) j=1;
if (a[k]==yao1) jj=1;
itoa(a[k],ms,10);
ch=ms[0];;
fputc(ch,fp);
fputc(' ',fp);
printf("%d ",a[k]);}
fputc('\n',fp);
printf("\n");
if (j==1 && jj==1) {
for (k=5;k>=0;k--) b[kk][k]=a[k];kk++;}
j=jj=0;
}
}
}
}
}
}
}
printf("the locked groups are: ");
for (j=0;j<kk;j++) {
for (jj=5;jj>=0;jj--) printf("%d ",b[j][jj]);
printf("\n");}

fclose(fp);getch();

}

Answer 3

用回溯和一个全局数组jilu[]来记录,
用另外一个全局数组a[34]={0}来确定该数是否已经用过,0为没用过,1为用过
全局变量i来作为jilu[]的下标,从0开始,到6结束;sum=0来记录总值

程序框架:

int jilu[7]={0};
int a[34]={0};
int i=1,sum=0;
void chazhao(int k){//为了省略排序和重复，只找比k大的数
int j;
if(i==6 && sum==x)
弄个循环确定里面是否有你一定要有的数，如果有就输出;
else if(i<=5 && sum<x){
if(i==0)
for(j=1;j<=28;j++){ //因为只找比k大的数字,所以确定第一个数字时，最大到28
i++;
a[j]=1;
jilu[i]=j;
sum=sum+j;

chazhao(j);

sum=sum-j; //恢复
a[j]=0;
jilu[i]=0;
i--;
}
else{
for(j=k;j<=33;j++)
if(a[j]==0){//没被用过
i++;
jilu[i]=j;
a[j]=1;
sum=sum+j;

chazhao(j);

sum=sum-j;
a[j]=0; //恢复
jilu[i]=0;
i--;
}
}
}
}

void main(){
初始化啥的
chazhao(1);
}

Answer 4

#include <stdio.h>
void main()
{
int a,b,c,d,e,f,sum,i=0,y=0;
printf("Plsase input the six numbers'sum:");
scanf("%d",&sum);
printf("If U request fix a number plsese input(if U no request\n please input \"0\":");
scanf("%d",&y);
for(a=1;a<=sum&&a<=33;a++)
{
for(b=a+1;b<=sum-a&&b<=33;b++)
{
for(c=b+1;c<=sum-a-b&&c<=33;c++)
{
for(d=c+1;d<=sum-a-b-c&&d<=33;d++)
{
for(e=d+1;e<=sum-a-b-c-d&&e<=33;e++)
{
for(f=e+1;f<=sum-a-b-c-d-e&&f<=33;f++)
if(a+b+c+d+e+f==sum)
{
if(y==0)
printf("The six numbers is: %2d %2d %2d %2d %2d %2d\n",f,e,d,c,b,a);
else
if(a==y||b==y||c==y||d==y||e==y||f==y)
printf("The six numbers is: %2d %2d %2d %2d %2d %2d\n",f,e,d,c,b,a);
i=1;
}
}
}
}
}
}
if(i==0)
printf("Don't exist the six numbers");
getch();
}

对不起，我还不会保存，而且只能让程序固定一个数

Answer 5

直接用深度优先搜索