找回密码
 欢迎注册
楼主: northwolves

[擂台] Ten digit numbers

[复制链接]
 楼主| 发表于 2009-1-12 16:54:48 | 显示全部楼层
恭候佳音
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-12 17:06:08 | 显示全部楼层
原帖由 无心人 于 2009-1-12 16:22 发表

#include
#include
#include
   
int test(mpz_t pow, int p)
{
  unsigned tmp;
  int d[10], i;
  char t[250];
  for (i = 0; i < 10; i ++) d = 0;

  mpz_get_str(t, 10, pow);
  for (i = 0 ...


n个0-9的数字和一定是9的倍数,所以满足条件的10位数一定是3的倍数,可提速2倍。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 17:26:57 | 显示全部楼层
我倒是觉得可以批量一起搜索多个幂的情况,比如

  1. #define MAX_TIMES 30
  2. int TIMES=20;

  3. int cc[MAX_TIMES+1];

  4. void check(integer& x,integer& y, int k)
  5. {
  6.     LPCTSTR s=y.GetStr(FS_NORMAL);
  7.     int i;
  8.     int count[10];
  9.     int tc=0;
  10.     for(i=0;i<10;i++)count[i]=0;
  11.     for(i=0;s[i]!='\0';i++){
  12.         if('0'<=s[i]&&s[i]<='9'){
  13.             int h=s[i]-'0';
  14.             count[h]++;tc++;
  15.             if(count[h]>k)return;
  16.         }
  17.     }
  18.     if(count[0]+10*k-tc!=k)return;
  19.     cc[k]++;
  20.     printf("%s^%d=%s\n",x.GetStr(FS_NORMAL),k,s);
  21.     fflush(stdout);
  22. }
  23. integer yt[MAX_TIMES+1];
  24. char buf1[1000];
  25. char buf2[1000];
  26. void test()
  27. {
  28.     time_t t=time(NULL);
  29.     integer x(1);
  30.     long long u=1LL;
  31.     int i,mt;
  32.     int c=0;
  33.     for(i=0;i<10;i++){
  34.         x*=10;
  35.         u*=10LL;
  36.     }
  37.     integer y(x);
  38.     y/=10;
  39.     for(i=1;i<=MAX_TIMES;i++){
  40.         yt[i]=y;
  41.         y*=x;
  42.     }
  43.     x--;u--;
  44.     mt=MAX_TIMES;
  45.     for(;u>0LL;x-=3,u-=3LL){
  46.         integer z(x);
  47.         for(i=2;i<=mt;i++){
  48.             z*=x;
  49.             strcpy(buf1,z.GetStrA(FS_NORMAL,NULL));
  50.             strcpy(buf2,yt[i].GetStrA(FS_NORMAL,NULL));
  51.             if(z<yt[i]){mt=i-1;break;}
  52.             check(x,z,i);
  53.         }
  54.         if(i<=2)break;
  55.         c++;
  56.         if(c%100000==0){
  57.             time_t now=time(NULL);
  58.             fprintf(stderr,"%lld, times %ds\n",u,(int)(now-t));
  59.         }
  60.     }
  61.     t=time(NULL)-t;
  62.     printf("Total cost %dseconds\n",t);
  63. }

  64. int main(int argc, char* argv[])
  65. {
  66.     int i;
  67.     test();
  68.     for(i=2;i<=MAX_TIMES;i++){
  69.         printf("c[%d]=%d\n",i,cc[i]);
  70.     }
  71.     return 0;
  72. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 20:22:39 | 显示全部楼层
mathe 的批量搜索的想法很好,可以减少总体计算总量。

下面是我写的单独搜索某个幂次的代码,局部做过一些优化,比如在统计每个数字的数量判断上:
  1. //  Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
  2. //      Win32 Debug:    Debug Multithreaded DLL
  3. //      Win32 Release:  Multithreaded DLL

  4. #include <stdio.h>

  5. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"    // 公共接口
  6. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"    // 10进制系统

  7. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  8. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )

  9. int main(int argc, char* argv[])
  10. {
  11.     UINT32 i, count = 0;
  12.     UINT32 r, digits;
  13.     UINT32 histogram[ 256 ] = { 0 };
  14.     LPCTSTR p;
  15.     CHugeInt hugePow, hugeBase( "10000000002" );  // 10000000002 % 3 == 0

  16.     printf( "Call %s\n", HugeCalc::GetVer());
  17.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
  18.     {
  19.         printf( "\n警告:您未通过 HugeCalc.dll 的许可认证!\n" \
  20.                 "\n解决方案可选下列方案之一:" \
  21.                 "\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行;" \
  22.                 "\n    二、或请在 HugeCalc.chm 中进行注册(一劳永逸)。\n\n" );

  23.         system( "pause" );
  24.         return (-1);
  25.     }

  26.     printf( "\nr = ");
  27.     scanf( "%u", &r );

  28.     HugeCalc::EnableTimer( TRUE );
  29.     HugeCalc::ResetTimer();

  30.     digits = r * 10;

  31.     for ( ; ; )
  32.     {
  33.         hugePow.Pow( hugeBase -= 3UL, r );
  34.         if ( digits != hugePow.GetDigits() )
  35.             break;

  36.         histogram[ '\0' ] = 1;
  37.         for ( i = '0'; i <= '9'; ++i )
  38.             histogram[ i ] = r + 1;

  39.         for ( p = hugePow; 0 != --histogram[ *p ]; ++p )
  40.             ;

  41.         if ( '\0' == *p )
  42.             printf( "%s\tNo.%u\t%s\n", HugeCalc::GetTimerStr( FT_HHMMSS_ms ), ++count, (LPCTSTR)hugeBase );
  43.     }

  44.     printf( "\n****** %s ******\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
  45.     system( "pause" );

  46.     return 0;
  47. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 22:01:43 | 显示全部楼层


呵呵, 米想那么多
明天去优化下

因为感觉这个问题的幂并不很高
理论上不会超过10^8次幂
实际上可能在20以上就会有很多幂没结果了

明天看有时间么?
有时间打算用17台机器一起跑
最好1个小时算完
应该能搜索完40次幂以下的所有结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 22:03:20 | 显示全部楼层
肚子的代码很奇怪?
什么库?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 22:28:14 | 显示全部楼层
原帖由 northwolves 于 2009-1-12 14:24 发表


我只算到20,当初按概率统计认为不会出现大于20 的数了。
后来发现,最小值当n=26时还找到一个值,也许不止一个。

n=21,9766102146
n=22,9863817738
n=24,9793730157
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 22:29:32 | 显示全部楼层
原帖由 无心人 于 2009-1-12 22:03 发表
肚子的代码很奇怪?
什么库?

锅呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 22:31:58 | 显示全部楼层


呵呵
你怎么知道肚子指的是你?


哎, 不要你们去算20-23的结果
和我在学校挂的20-23的程序冲突了
浪费掉了资源
这三个是唯一的么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 22:42:01 | 显示全部楼层
原帖由 无心人 于 2009-1-12 22:31 发表


呵呵
你怎么知道肚子指的是你?


哎, 不要你们去算20-23的结果
和我在学校挂的20-23的程序冲突了
浪费掉了资源
这三个是唯一的么?

northwolves的序列,最大的一个。
我用的很慢的一台老机器,从大的数字开始搜索,如上面代码,同时计算2次幂到30次幂。反正这个序列应该这几天就可以被解决了,先抢先贴几个数字再说
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 08:45 , Processed in 0.044015 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表