无心人 发表于 2009-1-7 14:33:43

我想了
如果淘汰，必然要用浮点运算，是否合算，并不是很确定

另外，40位的候选并不是很多，4亿左右

medie2005 发表于 2009-1-7 14:58:50

原帖由 无心人 于 2009-1-7 14:33 发表 http://bbs.emath.ac.cn/images/common/back.gif
另外，40位的候选并不是很多，4亿左右
怎么算出来的?:Q: :lol

无心人 发表于 2009-1-7 15:09:04

终于正确了，在计算中#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

#define base100000000
#define ds 5

int powD;
int sum;
int num;
int N;
struct timeval start, end;

void init(void)
{
int i, j, k;

for (i = 0; i <= 9; i ++)
    for (j = 0; j < ds; j ++)
      powD = 0;

for (i = 0; i <= 9; i ++)
    num = 0;

for (i = 1; i <= 9; i ++)
    powD = i;
}

void nextPower(void)
{
   int i, j, t;
   for (i = 2; i <= 9; i ++)
   {
       t = 0;
       for (j = 0; j < ds; j ++)
       {
         t = powD * i + t;
         if (t >= base)
         {
               powD = t % base;
               t /= base;
         }
         else
         {
               powD = t;
               t = 0;
         }
       }
   }
}

int circle(int n, int b)
{
int i, j, k;
double tm;

if (n == 0)
{
    if (sort())
    {
      k = ds - 1;
      while ((sum == 0) && (k >= 0))
      k --;
      gettimeofday(&end, NULL);
      tm = (end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec);
      tm /= 1000000.0;
      printf("%4.4f", tm);
      printf("%2d: ", N);
      printf("%d", sum);
      if (k > 0)
      for (i = k - 1; i >= 0; i --)
          printf("%08d", sum);
      printf("\n");
    }
}
else
   for (i = 0; i <= b; i ++)
   {
       num ++;
           circle(n-1, i);
       num --;
   }
}


int sort(void)
{
int i, j, t;
int temp, d;

for (i = 0; i < ds; i ++)
    temp = sum = 0;

for (i = 0; i <= 9; i ++)
    d = 0;

for (i = 1; i <= 9; i ++)
    if (num)
    {
      t = 0;
      for (j = 0; j < ds; j ++)
      {
      t = powD * num + t;
      if (t >= base)
      {
            temp = t % base;
            t /= base;
      }
      else
      {
            temp = t;
            t = 0;
      }
      }
      
      t = 0;
      for (j = 0; j < ds; j++)
      {
      t = temp + sum + t;
      if (t >= base)
      {
            sum = t - 100000000;
            t = 1;
      }
      else
      {
            sum = t;
            t = 0;
      }
      }
    }
   
    for (i = ds - 1; i >= 0; i --)
    {
      t = sum;
      if (t > 0)
          while (t > 0)
          {
            d ++;
            t /= 10;
          }
    }
   
    for (i = 1; i <= 9; i ++)
      if (num != d)return 0;
    return 1;
}

int main(void)
{
int i, j;

gettimeofday(&start, NULL);
init();
nextPower(); //是平方
for (i = 2; i <= 40; i ++)
{
    N = i;
    printf("Search %d...\n", i);
    circle(N, 9);
    nextPower();
}
return 0;      
}

无心人 发表于 2009-1-7 15:09:35

完全的结果

=======================
E:\MinGW\MSYS\math>hg
Search 2...
0.0000   2: 0
0.0000   2: 1
Search 3...
0.0000   3: 0
0.0000   3: 1
0.0000   3: 153
0.0000   3: 370
0.0000   3: 371
0.0000   3: 407
Search 4...
0.0000   4: 0
0.0000   4: 1
0.0000   4: 1634
0.0000   4: 8208
0.0000   4: 9474
Search 5...
0.0000   5: 0
0.0000   5: 1
0.0000   5: 4150
0.0000   5: 4151
0.0000   5: 54748
0.0000   5: 92727
0.0000   5: 93084
Search 6...
0.0000   6: 0
0.0000   6: 1
0.0000   6: 548834
Search 7...
0.0000   7: 0
0.0000   7: 1
0.0000   7: 1741725
0.0000   7: 4210818
0.0000   7: 9800817
0.0000   7: 9926315
Search 8...
0.0000   8: 0
0.0000   8: 1
0.0000   8: 24678050
0.0000   8: 24678051
0.0000   8: 88593477
Search 9...
0.0156   9: 0
0.0156   9: 1
0.0156   9: 146511208
0.0156   9: 472335975
0.0156   9: 534494836
0.0156   9: 912985153
Search 10...
0.031310: 0
0.031310: 1
0.046910: 4679307774
Search 11...
0.062511: 0
0.062511: 1
0.093811: 32164049650
0.093811: 32164049651
0.093811: 40028394225
0.093811: 42678290603
0.093811: 44708635679
0.093811: 49388550606
0.109411: 82693916578
0.109411: 94204591914
Search 12...
0.125012: 0
0.125012: 1
Search 13...
0.234413: 0
0.234413: 1
0.265613: 564240140138
Search 14...
0.421914: 0
0.421914: 1
0.578114: 28116440335967
Search 15...
0.734415: 0
0.734415: 1
Search 16...
1.312516: 0
1.312516: 1
1.937516: 4338281769391370
1.937516: 4338281769391371
Search 17...
2.203117: 0
2.203117: 1
2.250017: 233411150132317
2.890617: 21897142587612075
3.078117: 35641594208964132
3.093817: 35875699062250035
Search 18...
3.562518: 0
3.562518: 1
Search 19...
5.656319: 0
5.656319: 1
6.953219: 1517841543307505039
7.812519: 3289582984443187032
8.171919: 4498128791164624869
8.218819: 4929273885928088826
Search 20...
8.828220: 0
8.828220: 1
13.015720: 63105425988599693916
Search 21...
13.484521: 0
13.484521: 1
16.281421: 128468643043731391252
19.093921: 449177399146038697307
Search 22...
20.312622: 0
20.312622: 1
Search 23...
30.187723: 0
30.187723: 1
39.250323: 21887696841122916288858
40.437823: 27879694893054074471405
40.469023: 27907865009977052567814
40.531523: 28361281321319229463398
41.125323: 35452590104031691935943
Search 24...
44.765924: 0
44.781524: 1
56.437924: 174088005938065293023722
57.125424: 188451485447897896036875
57.500424: 239313664430041569350093
Search 25...
64.609825: 0
64.609825: 1
69.078625: 114735624485461118832514
75.250525: 832662335985815242605070
75.250525: 832662335985815242605071
80.125525: 1550475334214501539088894
80.328625: 1553242162893771850669378
88.609925: 3706907995955475988644380
88.609925: 3706907995955475988644381
89.922525: 4422095118095899619457938
Search 26...
92.766226: 0
92.766226: 1
Search 27...
131.360227: 0
131.360227: 1
139.172827: 7584178683470015004720746
153.032227: 77888878776432530886487094
157.376027: 121204998563613372405438066
157.563527: 121270696006801314328439376
160.172927: 128851796696487777842012787
162.329227: 174650464499531377631639254
163.891727: 177265453171792792366489765
Search 28...
182.782428: 0
182.782428: 1
Search 29...
254.657929: 0
254.657929: 1
267.329829: 477144170826130800418527003
277.361229: 4716716265341543230394614213
283.392429: 5022908050052864745436221003
313.845829: 14607640612971980372614873089
320.517729: 19008174136254279995012734740
320.517729: 19008174136254279995012734741
328.814629: 23866716435523975980390369295
Search 30...
347.908530: 0
347.908530: 1
Search 31...
470.221831: 0
470.221831: 1
547.862931: 793545620525277858657607629822
558.988031: 1145037275765491025924292050346
596.519431: 1927890457142960697580636236639
606.253931: 2309092682616190307509695338915
Search 32...
634.379132: 0
634.379132: 1
793.677032: 17333509997782249308725103962772
Search 33...
841.505433: 0
841.505433: 1
916.896533: 32186410459473623435614002227248
1062.178733: 186709961001538790100634132976990
1062.694333: 186709961001538790100634132976991
Search 34...
1114.288434: 0
1114.288434: 1
1348.118034: 1122763285329372541592822900204593
Search 35...
1471.103235: 0
1471.103235: 1
1676.963935: 5250083909873201044638631458484846
1722.995435: 7673249664848285722449710136138169
1796.699035: 12639369517103790328947807201478392
1799.699035: 12679937780272278566303885594196922
Search 36...
1910.934136: 0
1910.934136: 1
2276.030236: 91097771122214850683543503173498149
Search 37...
2475.562737: 0
2475.562737: 1
2790.002237: 418510620208153136884574959404115822
2869.424637: 618670315011216949642642321868915308
3027.488137: 1219167219625434121569735803609966019
Search 38...
3200.973638: 0
3200.973638: 1
3736.164538: 7320233109580046612992702336326619665
3772.914838: 7403697806790834730831423191927508283
3927.681438: 12815792078366059955099770545296129367
Search 39...
4088.807439: 0
4088.807439: 1
4307.558839: 16427762135335641330720936105651700735
4904.640839: 83281823928125880164896079973522049472
4904.781439: 83281830613691836766959173718984508549
4999.625739: 115132219018763992565095597973971522400
4999.625739: 115132219018763992565095597973971522401
Search 40...
5223.642840: 0
5223.642840: 1
====================================================
可惜没输出最终时间
呵呵

无心人 发表于 2009-1-7 16:09:55

呵呵
打算修改下
连扩展的一起算

从41算到64，是否可行呢？

无心人 发表于 2009-1-7 17:02:23

好像核验的结果不对？？
谁能提供第三方核验

medie2005 发表于 2009-1-7 17:43:50

3 digits search start!
153
407
370
371
4 digits search start!
1634
8208
9474
5 digits search start!
54748
93084
92727
6 digits search start!
548834
7 digits search start!
1741725
4210818
9926315
9800817
8 digits search start!
24678050
24678051
88593477
9 digits search start!
146511208
912985153
534494836
472335975
10 digits search start!
4679307774
11 digits search start!
82693916578
94204591914
40028394225
44708635679
42678290603
49388550606
32164049651
32164049650
12 digits search start!
13 digits search start!
14 digits search start!
28116440335967
15 digits search start!
16 digits search start!
4338281769391371
4338281769391370
17 digits search start!
35875699062250035
35641594208964132
21897142587612075
18 digits search start!
19 digits search start!
3289582984443187032
4498128791164624869
4929273885928088826
1517841543307505039
20 digits search start!
63105425988599693916
21 digits search start!
449177399146038697307
128468643043731391252
22 digits search start!
23 digits search start!
21887696841122916288858
35452590104031691935943
28361281321319229463398
27907865009977052567814
27879694893054074471405
24 digits search start!
188451485447897896036875
174088005938065293023722
239313664430041569350093
25 digits search start!
1550475334214501539088894
1553242162893771850669378
4422095118095899619457938
3706907995955475988644380
3706907995955475988644381
26 digits search start!
27 digits search start!
121270696006801314328439376
121204998563613372405438066
128851796696487777842012787
177265453171792792366489765
174650464499531377631639254
28 digits search start!
29 digits search start!
19008174136254279995012734741
19008174136254279995012734740
23866716435523975980390369295
14607640612971980372614873089
30 digits search start!
31 digits search start!
2309092682616190307509695338915
1927890457142960697580636236639
1145037275765491025924292050346
32 digits search start!
17333509997782249308725103962772
33 digits search start!
186709961001538790100634132976990
186709961001538790100634132976991
34 digits search start!
1122763285329372541592822900204593
35 digits search start!
12639369517103790328947807201478392
12679937780272278566303885594196922
36 digits search start!
37 digits search start!
1219167219625434121569735803609966019
38 digits search start!
12815792078366059955099770545296129367
39 digits search start!
115132219018763992565095597973971522401
115132219018763992565095597973971522400
time : 3830016 ms
press any key to continue...

无心人 发表于 2009-1-7 18:24:07

似乎和 我的一致
但我找到的扩展回归数你没有搜索
我的不知道是否对
给出你的程序吧

medie2005 发表于 2009-1-8 09:15:06

扩展回归数? 定义是什么?

mathe 发表于 2009-1-8 09:22:04

这个题目可优化的机会应该很小,只是位数比较大的时候,可以事先淘汰掉很多组合.
比如如果发现某种组合计算结果太大了(比如一个含有30个数字的组合结果之和大于30位数),那么同样数目数字的组合中,每个数字都不小于这个组合的那些就可以淘汰掉了.
页: 1 [2] 3 4 5 6
查看完整版本: 回归数