#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: 不知道我這些方法叫不叫"全真模擬選號"...