数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › Ten digit numbers
12345678910... 13下一页
返回列表 发新帖
楼主: northwolves

[擂台] Ten digit numbers

[复制链接]
northwolves
 楼主| 发表于 2009-1-12 16:54:48 | 显示全部楼层
恭候佳音
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

northwolves
 楼主| 发表于 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倍。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-1-12 17:26:57 | 显示全部楼层
我倒是觉得可以批量一起搜索多个幂的情况，比如
  2. #define MAX_TIMES 30
  3. int TIMES=20;
  5. int cc[MAX_TIMES+1];
  7. void check(integer& x,integer& y, int k)
  8. {
  9. LPCTSTR s=y.GetStr(FS_NORMAL);
  10. int i;
  11. int count[10];
  12. int tc=0;
  13. for(i=0;i<10;i++)count[i]=0;
  14. for(i=0;s[i]!='\0';i++){
  15. if('0'<=s[i]&&s[i]<='9'){
  16. int h=s[i]-'0';
  17. count[h]++;tc++;
  18. if(count[h]>k)return;
  19. }
  20. }
  21. if(count[0]+10*k-tc!=k)return;
  22. cc[k]++;
  23. printf("%s^%d=%s\n",x.GetStr(FS_NORMAL),k,s);
  24. fflush(stdout);
  25. }
  26. integer yt[MAX_TIMES+1];
  27. char buf1[1000];
  28. char buf2[1000];
  29. void test()
  30. {
  31. time_t t=time(NULL);
  32. integer x(1);
  33. long long u=1LL;
  34. int i,mt;
  35. int c=0;
  36. for(i=0;i<10;i++){
  37. x*=10;
  38. u*=10LL;
  39. }
  40. integer y(x);
  41. y/=10;
  42. for(i=1;i<=MAX_TIMES;i++){
  43. yt[i]=y;
  44. y*=x;
  45. }
  46. x--;u--;
  47. mt=MAX_TIMES;
  48. for(;u>0LL;x-=3,u-=3LL){
  49. integer z(x);
  50. for(i=2;i<=mt;i++){
  51. z*=x;
  52. strcpy(buf1,z.GetStrA(FS_NORMAL,NULL));
  53. strcpy(buf2,yt[i].GetStrA(FS_NORMAL,NULL));
  54. if(z<yt[i]){mt=i-1;break;}
  55. check(x,z,i);
  56. }
  57. if(i<=2)break;
  58. c++;
  59. if(c%100000==0){
  60. time_t now=time(NULL);
  61. fprintf(stderr,"%lld, times %ds\n",u,(int)(now-t));
  62. }
  63. }
  64. t=time(NULL)-t;
  65. printf("Total cost %dseconds\n",t);
  66. }
  68. int main(int argc, char* argv[])
  69. {
  70. int i;
  71. test();
  72. for(i=2;i<=MAX_TIMES;i++){
  73. printf("c[%d]=%d\n",i,cc[i]);
  74. }
  75. return 0;
  76. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 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
  5. #include <stdio.h>
  7. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
  8. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
  10. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  11. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  13. int main(int argc, char* argv[])
  14. {
  15. UINT32 i, count = 0;
  16. UINT32 r, digits;
  17. UINT32 histogram[ 256 ] = { 0 };
  18. LPCTSTR p;
  19. CHugeInt hugePow, hugeBase( "10000000002" ); // 10000000002 % 3 == 0
  21. printf( "Call %s\n", HugeCalc::GetVer());
  22. if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
  23. {
  24. printf( "\n警告：您未通过 HugeCalc.dll 的许可认证！\n" \
  25. "\n解决方案可选下列方案之一：" \
  26. "\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
  27. "\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\n\n" );
  29. system( "pause" );
  30. return (-1);
  31. }
  33. printf( "\nr = ");
  34. scanf( "%u", &r );
  36. HugeCalc::EnableTimer( TRUE );
  37. HugeCalc::ResetTimer();
  39. digits = r * 10;
  41. for ( ; ; )
  42. {
  43. hugePow.Pow( hugeBase -= 3UL, r );
  44. if ( digits != hugePow.GetDigits() )
  45. break;
  47. histogram[ '\0' ] = 1;
  48. for ( i = '0'; i <= '9'; ++i )
  49. histogram[ i ] = r + 1;
  51. for ( p = hugePow; 0 != --histogram[ *p ]; ++p )
  52. ;
  54. if ( '\0' == *p )
  55. printf( "%s\tNo.%u\t%s\n", HugeCalc::GetTimerStr( FT_HHMMSS_ms ), ++count, (LPCTSTR)hugeBase );
  56. }
  58. printf( "\n****** %s ******\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
  59. system( "pause" );
  61. return 0;
  62. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2009-1-12 22:01:43 | 显示全部楼层
呵呵， 米想那么多 明天去优化下 因为感觉这个问题的幂并不很高 理论上不会超过10^8次幂 实际上可能在20以上就会有很多幂没结果了 明天看有时间么? 有时间打算用17台机器一起跑 最好1个小时算完 应该能搜索完40次幂以下的所有结果
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2009-1-12 22:03:20 | 显示全部楼层
肚子的代码很奇怪？ 什么库？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 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
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-1-12 22:29:32 | 显示全部楼层
原帖由 无心人 于 2009-1-12 22:03 发表 肚子的代码很奇怪？ 什么库？
锅呀
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2009-1-12 22:31:58 | 显示全部楼层
呵呵 你怎么知道肚子指的是你？ 哦 哎， 不要你们去算20-23的结果 和我在学校挂的20-23的程序冲突了 浪费掉了资源 这三个是唯一的么？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-1-12 22:42:01 | 显示全部楼层
原帖由 无心人 于 2009-1-12 22:31 发表 呵呵 你怎么知道肚子指的是你？ 哦 哎， 不要你们去算20-23的结果 和我在学校挂的20-23的程序冲突了 浪费掉了资源 这三个是唯一的么？
northwolves的序列，最大的一个。 我用的很慢的一台老机器，从大的数字开始搜索，如上面代码，同时计算2次幂到30次幂。反正这个序列应该这几天就可以被解决了，先抢先贴几个数字再说
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

12345678910... 13下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-21 21:27 , Processed in 0.031368 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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