• ベストアンサー
  • 暇なときにでも

改善すべき点を教えてください。

趣味で最近Cを始めたのですが、ある本で「0を除く2種類の数字のみで構成された平方数」は、81619の二乗(6661661161)より大きいものはないらしい。 と書かれていたので、確かめたくなり色々調べながらプログラミングしてみました。 なんとか動くようになったのですが、いまいちスピードが遅いように感じるのです。 そこで、こうすればスピードを速くできる、ここが不自然な書き方になっているなど、どこか改善すべき点があれば教えて欲しく質問しました。 あと、char型からint型に数字を変換する時に恐らく不自然な方法でやっているので、正規の方法がありましたらそれも教えていただけると助かります。 よろしくおねがいします。 ここから――――――――――――――――――――――― #include <stdio.h> #include <string.h> int main(void){   double i;    //平方根   int m;    //整数(for用)   double x;  //平方数   char str[100];  //文字列(途中作業用)   int mono[100];  //1桁の数字(途中作業用)   int len;  //桁数   int num;  //二つ目の数の置場      for( i=1; i<=10000000000; i++){     x=i*i;              //二乗     sprintf(str,"%.0f",x);      //文字列に平方数を変換     len=strlen(str);         //桁数を求める          if(len<=1)       goto PRINT;          //平方数が一桁ならPRINTへ          for( m=0; m<len; m++){       mono[m]=str[m]-48;      //一桁ずつint型に収納+実際の数に調整。     }          m=(int)i;     if( m%2000000==0)       printf("i=%32.0f:ok - ",i);  //進行状況          for( m=0; m<len; m++)       if( mono[m]==0)         goto OUT;         //0が含まれていたらOUTへ     for( m=1; m<len; m++){       if( mono[m]==mono[0])         goto WHENSAME;      //mono[0]と同じ数字だったらWHENSAMEへ       num=m;            //違う数字の一回目の登場場所をnumに代入       break;            // →脱出       WHENSAME:           //ラベル WHENSAME     }     for( m=num+1; m<len; m++){       if( mono[m]==mono[0]);       else if( mono[m]==mono[num]);       else         goto OUT;       }     PRINT:              //ラベル PRINT     printf("%5.0f => %26.0f\n", i, x);     OUT:               //ラベル OUT   }   return 0; }

共感・応援の気持ちを伝えよう!

  • 回答数10
  • 閲覧数676
  • ありがとう数9

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.2

★アドバイス >なんとか動くようになったのですが、いまいちスピードが遅いように感じるのです。 >そこで、こうすればスピードを速くできる、ここが不自然な書き方になっているなど、 >どこか改善すべき点があれば教えて欲しく質問しました。  ↑  回答者 No.1 さんのアドバイス以外にも  (1)キャストをつけて見る   修正前⇒len=strlen(str);     //桁数を求める   修正後⇒len=(int)strlen(str);  //桁数を求める  ※strlen() 関数の戻り値は size_t 型なので int 型に結果を代入するときはキャストする。  (2)ラベルの『:』文字の次に空文『;』を追加   修正前⇒WHENSAME:           //ラベル WHENSAME   修正後⇒WHENSAME:;           //ラベル WHENSAME      修正前⇒OUT:               //ラベル OUT   修正後⇒OUT:;               //ラベル OUT  ※ラベルの後に『文』がない場合はエラーとなります。そのため空文の『;』を挿入する。  (3)WHENSAME ラベルは continue でも代用できます。   修正後のみ   for ( m = 1 ; m < len ; m++ ){     if ( mono[m] == mono[0] )       continue;      //mono[0]と同じ数字だったらWHENSAMEへ     num = m;         //違う数字の一回目の登場場所をnumに代入     break;          // →脱出   }   または   for ( m = 1 ; m < len ; m++ ){    if ( mono[m] != mono[0] ){  //mono[0]と同じ数字だったらWHENSAMEへ     num = m;          //違う数字の一回目の登場場所をnumに代入     break;          // →脱出    }   }   としてみる。  (4)ちょっと細かいが定数値 48 よりも '0' で記述   修正前⇒mono[m]=str[m]-48;      //一桁ずつint型に収納+実際の数に調整。   修正後⇒mono[m]=str[m]-'0';      //一桁ずつint型に収納+実際の数に調整。  ※分かりやすく文字定数で記述してみる。48 よりも '0' が分かりやすいはず。  (5)double 型は使わずにすべてを整数型で処理   i カウンタが 1~10^10 ですが二乗すると 10^20 となります。   64ビット整数(long long型)を使ってもオーバーフローを起こすため最大でも 10^9 乗に   抑えてから計算します。どんなコンパイラを使っているのか分かりませんが、64ビットの   整数型(long long型)が利用できるのならば double x; ではなくて long long x; として   処理してみて下さい。 ・計算量が多いのであまり高速にならない気がします。パソコンの限界?かと。 ・以上。整数型(longか long long 型など)で処理するように書き換えてみて下さい。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

> (1)(2)(3)(4) なるほど…勉強になります。 ありがとうございます。 > (5) > 64ビットの整数型(long long型)が利用できるのならば double x; ではなくて long long x; として処理 long long x; という風に使うんですね;; 今やってみましたが「宣言に型が多すぎる(関数 main())」とエラーが出ます。。 これは使えないということなのでしょうか…? コンパイラですが、Borland C++Compiler 5.5.1 を使っています。

関連するQ&A

  • テキストファイルから読み込ませたい

    このプログラムをテキストファイルから読み込ませたいのですが、 どう改良したらいいかわかりません。どなたかプログラムの追加を教えていたたけないでしょうか。 #include <stdio.h> int main() { int i,key,len,num ; char str[256],*ptr[128] ; num = 0 ; len = 0 ; ptr[0] = str ; do { key = getchar(); str[len] = (char)key ; if ( key == ' ' || key == '.' || key == ',' || key == '!' || key == '?' || key == '"' || key == 0x0a || key == 0x0d ){ str[len] = '\0' ; if ( str+len-ptr[num] ){ num ++ ; } ptr[num] = str+len+1 ; if( key=='.' || key== '!' || key=='?' || key=='"'){ str[++len]=(char)key; str[++len]='\0'; ptr[++num]=&str[len+1]; } } len ++ ; } while ( key != 0x0a && key != 0x0d && len < 255 ); str[255] = '\0' ; for (i=0 ;i<num ;i++){ printf("%d. %s\n",i+1,ptr[i]); } return i ; }

  • 分割した単語の頻出頻度を表示させたい

    英文テキストファイルを読み込み、分割した単語の頻出頻度を表示するプログラムを作成しています。 現時点では、分割した単語の表示しかできていません。 どなたか良きアドバイスをお願いします。 #include <stdio.h> int main() { int i,key,len,num ; int sp=0; char str[100000],*ptr[100000] ; FILE *fp; if ((fp=fopen("test.txt","r"))==NULL) { return -1; } num = 0 ; len = 0 ; ptr[0] = str ; do { key = fgetc(fp); str[len] = (char)key ; if ( (key==' ' && sp==0) || key == '.' || key == ',' || key == '!' || key == '?' || key == '"' || key == 0x0a || key == 0x0d ){ str[len] = '\0' ; if ( str+len-ptr[num] ){ num ++ ; } ptr[num] = str+len+1 ; if( key==',' || key=='.' || key== '!' || key=='?' || key=='"'){ str[++len]=(char)key; str[++len]='\0'; ptr[++num]=&str[len+1]; } } sp= (key== ' ')?1:0; len ++ ; } while ( key != EOF && len < 255 ); str[255] = '\0' ; for (i=0 ;i<num ;i++){ printf("%s\n",ptr[i]); } fclose(fp); return i; }

  • このプログラムを改良したい

    この単語分割プログラムを区切り文字である( . ? ! " )等も一つの単語として表示させたいのですが、どう改良したらいいかわかりません。 どなたかプログラムの追加削除を教えていたたけないでしょうか。 #include <stdio.h> int main() { int i,key,len,num ; char str[256],*ptr[128] ; num = 0 ; len = 0 ; ptr[0] = str ; do { key = getchar(); str[len] = (char)key ; if ( key == ' ' || key == '.' || key == ',' || key == '!' || key == '?' || key == '"' || key == 0x0a || key == 0x0d ){ str[len] = '\0' ; if ( str+len-ptr[num] ){ num ++ ; } ptr[num] = str+len+1 ; } len ++ ; } while ( key != 0x0a && key != 0x0d && len < 255 ); str[255] = '\0' ; for (i=0 ;i<num ;i++){ printf("%d. %s\n",i+1,ptr[i]); } return i ; } *教えてgoo 質 問 No.919881 arukamunさんのプログラムを引用しました。

その他の回答 (9)

  • 回答No.10

★質問者さんと MASA_H さんへ。 ・いろいろと調べたらテーブル参照の方が遅かったです。  もう一つテーブルを用意して2段階にしても MASA_H さんのとほぼ同じ速度でした。  よって素直に回答者 No.9(MASA_H)さんの一つ一つ確認版が最終版ですかね。 ・下にそのソースを載せておきます。 最終版: #include <time.h> #include <stdio.h> // 2種類の数字のみで構成(MASA_Hより) int check_num( char ntmp[], int len ) {  char num[ 2 ];  int j;  num[ 0 ] = ntmp[ 0 ];    for ( j = 1 ; j < len ; j++ ){   num[ 1 ] = ntmp[ j ];      if ( num[0] != num[1] ){    break;   }  }  if ( num[0] == num[1] ){   return -1;  }  for ( j = 0 ; j < len ; j++ ){   if ( ntmp[j] == '0' || (ntmp[j] != num[0] && ntmp[j] != num[1]) ){    return (j + 1);   }  }  return 0; } // メイン関数 int main( void ) {  unsigned long long i, x; // 平方根  char str[ 100 ];   // 文字列(途中作業用)  int len, m, h, l;   // 桁数,ワーク変数  clock_t t;     // 計測用  clock_t start = clock(); // スタート用    for ( i = 1 ; i <= 1000000000 ; i++ ){   x = i * i;        // 二乗   len = sprintf( str, "%I64u", x );  // 文字列に平方数を変換      if ( (len == 1) || !check_num(str,len) ){    printf( "%5I64u => %20I64u\n", i, x );   }   // 進行状況   if ( !(i & 0x1FFFFF) ){    m = (int)(i / 100000);    h = (m / 100);    l = (m % 100);    t = (clock() - start);    printf( "i = %I64u(%d.%02d%%)%u.%03u秒\n", i, h, l, (t / 1000), (t % 1000) );   }  }  printf( "-- 終了 --\n" );  return 0; } 以上。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

後で10^8の時間を比較してみようかと思います^^ unsigned long long は ULONGLONG で置き換えると遅くなるとかいう事はないですよね。

質問者からの補足

欄が逆になってしまいますが、ここで最後のお礼をさせていただきます。 計測の結果はやはり質問時の方が早かったです…。 ただ、これから忙しくなり、お礼ができなくなると思いますので、勝手ながらここで締め切らせて頂きます。 最後に、回答してくれた皆様にお礼申し上げます。 ありがとうございました^^

  • 回答No.9
  • MASA_H
  • ベストアンサー率42% (64/151)

gcc+gprofで計測したところ、2種類の数字のみかどうかの判別はテーブルを使ったもの(Oh-Orangeさんのもの)より、一つ一つ確認していくもののほうが速かったです。 比較コード(これ以外は同じして比較した) テーブル版(table[1024]はグローバルにしてmain()内で初期化) int check_num(char ntmp[],int len){ int chk,m; for(chk=m=0;m<len;m++){ chk|=0x1<<(ntmp[m]-'0'); } if(!(chk&0x1)){ // 0が含まれない数を処理 if(table[chk]==2){ // 2種類の数字のみで構成 return(0); } } return(-1); } 一つ一つ確認版 int check_num(char ntmp[],int len){ char num[2]; int j; num[0]=ntmp[0]; for(j=1;j<len;j++){ num[1]=ntmp[j]; if(num[0]!=num[1])break; } if(num[0]==num[1])return(-1); for(j=0;j<len;j++){ if(ntmp[j]=='0'||(ntmp[j]!=num[0]&&ntmp[j]!=num[1])){ return(j+1); } } return(0); } 比較結果 テーブル版 % cumulative self self total time seconds seconds calls ns/call ns/call name 45.86 0.22 0.22 2147484 102.49 181.70 main_loop 35.43 0.39 0.17 2147484 79.20 79.20 check_num 18.76 0.48 0.09 main 0.00 0.48 0.00 1 0.00 0.00 init_table 一つ一つ確認版 % cumulative self self total time seconds seconds calls ns/call ns/call name 52.97 0.18 0.18 2147484 83.86 125.79 main_loop 26.48 0.27 0.09 2147484 41.93 41.93 check_num 20.60 0.34 0.07 main

共感・感謝の気持ちを伝えよう!

質問者からのお礼

計測していただきありがとうございました。 テーブルはここで初めて知ったので…これを機会に調べてみようかと思います^^

  • 回答No.8

★回答者 No.2、No.6、No.7 です。 >試してみたところ、(1)ではエラーが出ましたが他は出ませんでした。  ↑  (2)、(3)が使えるのならコンパイラを変える必要はないです。 >ちなみに、No.6で作って頂いたサンプルのi,xの宣言を >ULONG64 かULONGLONG にすればコンパイルでき、動作しました^^  ↑  実行結果も正しかったですか?  52行目の『x = i * i;』と  53行目の『len = sprintf( str, "%I64u", x );』  が正しかったら 64 ビット整数として計算できるため速度はどうですか。  double 型よりも早くなりましたか?  ※printf() の書式制御文字で64 ビット整数の『%I64u』が正しく使えるか調査。 >32行目:'value'に代入した値は使われていない >と警告が出るのですが、これは正常なのでしょうか?  ↑  この警告はおかしいですね。  initTable() 関数の for() 内で『value = i;』と代入して >table[ i ] = bit4count[ value & 0xF ]; value >>= 4; >table[ i ] += bit4count[ value & 0xF ]; value >>= 4; >table[ i ] += bit4count[ value & 0xF ]; value >>= 4;  として参照しているので警告が出るのはおかしい。  もし、警告が出るとすると上記の3行が記述されていないことになるが…。  記述していますよね? ・でも記述しているのならこの手の警告は無視して良いです。  無駄な変数が見つかったよ。とコンパイラさんが教えてくれているだけなので。  また、この警告が出るということはオプションで一番高く設定されていますね。  特に警告メッセージに問題はないです。 ・あと clock() 関数で時間を計測していますが表示とかに問題はありませんか?  特に問題が無ければ double 型や多倍長整数演算のものよりは早く計算できると  思います。私の環境では最初の『進行状況』が表示されるのに約3.1秒かかります。  この速度で終了するまで実行すると約36分かかりました。 ・あと main() 関数の for() 処理後に1行『printf( "-- 終了 --\n" );』を  追加しておいて下さい。追加しても、追加しなくてもどちらでも良いですけど。  その他、調べる数を『100000000(8個)』にすれば 200 秒ぐらいで終了しました。 ・以上。いろいろと試して見て下さい。 実行結果: 1 => 1 2 => 4 3 => 9 4 => 16 5 => 25 6 => 36 7 => 49 8 => 64 9 => 81 11 => 121 12 => 144 15 => 225 21 => 441 22 => 484 26 => 676 38 => 1444 88 => 7744 109 => 11881 173 => 29929 212 => 44944 235 => 55225 264 => 69696 3114 => 9696996 81619 => 6661661161 i = 2097152(0.20%)3.108秒 i = 4194304(0.41%)6.451秒 i = 6291456(0.62%)9.826秒 i = 8388608(0.83%)13.341秒 i = 10485760(1.04%)16.715秒  : i = 98566144(9.85%)196.918秒 -- 終了 --

共感・感謝の気持ちを伝えよう!

質問者からのお礼

計算結果は正しく出ました。 ただ、速度は10^8個を調べるのに1100秒かかりました。 clock()は動作していたので、質問時のものにclock()を付け加えて10^8個を計測したところ133秒でした…;; 64 ビット整数として計算できていないのでしょうか…。

  • 回答No.7

★追記。回答者 No.6 です。 ・簡単な多倍長整数演算を組み込んで試してみましたが double 型とほとんど速度に  変化が出ませんでした。どうやら double 型を使ったり、多倍長整数演算も含めて  速度に変化はあまり出ませんでした。 ・もし、もっと速度を上げて試したいのならば 64 ビット整数の long long 型が使える  コンパイラで実行して下さい。 >コンパイラですが、Borland C++Compiler 5.5.1 を使っています。  ↑  このコンパイラでは long long 型でエラーが出るため使えません。  よって マイクロソフト社の VC++2005 無料版をダウンロードして試せば long long 型が  使えるため回答 No.6 で速度を上げることが出来ます。  ただし、インストールなどの手間が増えますが…。 結果報告: ・回答 No.6 のソースで試した限りでは 1~100000000 で 81619 より大きいものは確かに  発見できませんでした。 ・実行時間はなんと 36 分もかかりました。→CPU使用率100% × 36分です。  『NEC ValueStar VL570/6 2.0GHz』  という環境です。 ・aniline さんの最初のソースでは 2000000 まで実行時間が約10秒かかりますが、  回答 No.6 のソースでは 2000000 まで実行時間が約2.9秒でした。  double 型や多倍長整数演算の場合も 2000000 まで実行時間が約10秒かかります。  ※ちなにみ clock() 関数で計測しました。 結論: >改善すべき点を教えてください。  ↑  いろいろソースをいじくるよりも単純に 64 ビット整数が利用できるコンパイラで  試した方が良さそうです。あるいはインライン・アセンブラを使って 64 ビットの  整数で計算させるとかします。 ・試しに次の型が利用できるか調べて見て下さい。  (1)__int64 型  (2)ULONG64 型  (3)ULONGLONG 型  (2)、(3)は windows.h をインクルードして下さい。  これらのデータ型が利用できるなら 64 ビット整数で試せます。  特に ULONGLONG 型が利用できるのならば UInt32x32To64() 関数が利用できます。  この関数は 32ビット整数×32ビット整数=64ビット整数の乗算を計算してくれます。 ・これを利用すれば  ULONGLONG x = UInt32x32To64( i, i );  として 64 ビット整数の乗算を行い  len = sprintf( str, "%I64u", x );  として文字列に変換すればよい。   ・以上。いろいろと試すか、コンパイラを変えるように。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

> 試しに次の型が利用できるか調べて見て下さい。 試してみたところ、(1)ではエラーが出ましたが他は出ませんでした。 初めて見たものなのでよくわからないのですが…新しいコンパイラに変える必要はないでしょうか…? ちなみに、No.6で作って頂いたサンプルのi,xの宣言をULONG64 かULONGLONG にすればコンパイルでき、動作しました^^ ただ、、 32行目:'value'に代入した値は使われていない と警告が出るのですが、これは正常なのでしょうか?

  • 回答No.6

★回答者 No.2 です。私も作ってみました。 ・テーブルを用いて2種類の数字かどうかを判定しています。  下の『全角文字』を一括して『タブ文字』に変換するとコメントが揃います。 ・あと long long 型が利用できないとエラーとなります。  この場合は x を double 型にして for のループを 10000000(10の7乗)にします。  その他 x 変数に関わる printf() の書式制御文字などを修正すればコンパイルが  可能になると思います。 ・それでは下にサンプルを載せておきます。 サンプル: #include <time.h> #include <stdio.h> #include <string.h> /* 10Bit(0~1023)のビットカウンタ数を初期化 */ void initTable( int table[] ) {  static int bit4count[] = {   0, // 0000   1, // 0001   1, // 0010   2, // 0011   1, // 0100   2, // 0101   2, // 0110   3, // 0111   1, // 1000   2, // 1001   2, // 1010   3, // 1011   2, // 1100   3, // 1101   3, // 1110   4, // 1111  }; int i, value;    for ( i = 0 ; i < 1024 ; i++ ){   value = i;   table[ i ] = bit4count[ value & 0xF ]; value >>= 4;   table[ i ] += bit4count[ value & 0xF ]; value >>= 4;   table[ i ] += bit4count[ value & 0xF ]; value >>= 4;  } } // メイン関数 int main( void ) {  char str[ 100 ];    //文字列(途中作業用)  unsigned long long i, x;  //平方根  int chk;      //チェック用  int len;      //桁数  int m;       //整数(for用)  int h, l;      //パーセント用  int table[ 1024 ];    //テーブル  clock_t start, t;    //計測用    // 初期化  initTable( table );  start = clock();    for ( i = 1 ; i <= 1000000000 ; i++ ){   x = i * i;        //二乗   len = sprintf( str, "%I64u", x );  //文字列に平方数を変換   if ( len == 1 ) goto PRINT;      // 数字の種類(0~9)を 10Bit に変換   for ( chk = m = 0 ; m < len ; m++ ){    chk |= 0x1 << (str[m] - '0');   }   if ( !(chk & 0x1) ){     // 0が含まれない数を処理    if ( table[chk] == 2 ){    // 2種類の数字のみで構成 PRINT:   printf( "%5I64u => %20I64u\n", i, x );    }   }   if ( !(i & 0x1FFFFF) ){     //進行状況    m = (int)(i / 100000);    //パーセント値(100.00%)    h = (m / 100);    l = (m % 100);    t = (clock() - start);    printf( "i = %I64u(%d.%02d%%)%d.%03d秒\n", i, h, l, (t / 1000), (t % 1000) );   }  }  return 0; } 以上。

共感・感謝の気持ちを伝えよう!

  • 回答No.5
  • zwi
  • ベストアンサー率56% (730/1282)

回答 No.3です。 gccで動作試してみましたが高速化してません。速度のネックは、やはりdoubleの計算と文字列に変換しているところにありそうです。 それとOUTのgotoは外さない方が高速化できそうなので残しました。 高速化のポイントは、for文のループ回数を出来るだけ減らすこと、if文の回数を減らすことなのですが、それ以外の部分で重いとさほど効果はありません。 clock()関数はgccなら問題ありませんが、bccで問題がある場合は外してください。 #include <stdio.h> #include <string.h> #include <time.h> int main(void){   double i;  //平方根   int m;    //整数(for用)   double x;  //平方数   char str[100];  //文字列(途中作業用)   int mono[100];  //1桁の数字(途中作業用)   int len;  //桁数   int num;  //二つ目の数の置場   unsigned long t0,t1;      t0 = clock();      for( i=1; i<=10000000000; i++){     x=i*i;              //二乗     sprintf(str,"%.0f",x);      //文字列に平方数を変換     len=strlen(str);        //桁数を求める      //※ この処理が無いほうが高速化できると思います。 //    if(len<=1) //      goto PRINT;         //平方数が一桁ならPRINTへ     for( m=0; m<len; m++) {       mono[m]=str[m]-48;      //一桁ずつint型に収納+実際の数に調整。     }            m=(int)i; //※ {}を書かないif文やfor文はプログラムの可読性が下がるので避けたほうがバグが減ります。     if( m%2000000==0) {       printf("i=%32.0f:ok - ",i);  //進行状況     }            num=0;     for( m=1; m<len; m++){ //※ 無理にひとつにまとめる必要も無いと思います。       if( mono[m]==0 ) {         goto OUT;//ループを抜けます。       } //※ num == 0を先の条件にした方が早くなります。条件不成立の場合は、後ろの条件をチェックしないため。       if( num==0 && mono[m]!=mono[0] ) {         num=m;       }       if( mono[m]!=mono[0] && mono[m]!=mono[num] ) {         goto OUT;//ループを抜けます。       }     }     t1 = clock();     printf("%5.0f => %26.0f time=%d \n", i, x, t1-t0); OUT:;   }   return 0; }

共感・感謝の気持ちを伝えよう!

質問者からのお礼

> {}を書かないif文やfor文はプログラムの可読性が下がるので避けたほうがバグが減ります。 以後気をつけようと思います^^ > num == 0を先の条件にした方が早くなります。条件不成立の場合は、後ろの条件をチェックしないため。 なるほど…、ためになります。 こういうところも注意して書かないとだめですね。 参考にしてまた見直してみようかと思います。 ありがとうございました。

  • 回答No.4
  • MASA_H
  • ベストアンサー率42% (64/151)

気分転換にGMPを使ったものを書いたので貼っときます。最適化も何も考えてないのでceleron2.6GHzで21474836個の探索をするのに12秒程度かかります。 #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <string.h> #include <gmp.h> #define SMAX INT_MAX/100 int main(void) { mpz_t x,y; char num[2],ntmp[32],ptmp[16]; int i,j,len,flag; mpz_init(x); mpz_init(y); mpz_set_ui(x,81619); for(i=0;i<=SMAX;i++){ flag=0; mpz_mul(y,x,x); mpz_get_str(ntmp,10,y); len=strlen(ntmp); num[0]=ntmp[0]; j=1; num[1]=ntmp[j]; while(1){ j++; if(j>=len){ flag=1; break; } if(num[0]!=num[1])break; num[1]=ntmp[j]; } if(flag==0){ for(j=0;j<len;j++){ if(ntmp[j]=='0'||(ntmp[j]!=num[0]&&ntmp[j]!=num[1])){ flag=j; break; } } } if(flag==0){ mpz_get_str(ptmp,10,x); printf("%s -> %s\n",ptmp,ntmp); } mpz_add_ui(y,x,1); mpz_set(x,y); if((i%2000000)==0)printf("(%d/%d)\n",i,SMAX); } mpz_clear(x); mpz_clear(y); return(0); }

共感・感謝の気持ちを伝えよう!

質問者からのお礼

>最適化も何も考えてないのでceleron2.6GHzで21474836個の探索をするのに12秒程度かかります。 皆さんの意見を参考に色々変えてみましたが、celeron1.6GHzで21474836個の探索が26秒かかりました。 質問時は35秒程度かかっていたので大分早くなりました^^ GMPはまだわかりませんが、導入したらまず参考にさせて頂きます。 回答ありがとうございました。

  • 回答No.3
  • zwi
  • ベストアンサー率56% (730/1282)

プログラムの問題点がいくつかあるので上げます。 ・gotoが多すぎます。if文の工夫やforループのcontinue文の導入で、全部のgoto文を一掃できます。 ・高速化のためにはループを減らしてください。下3つのfor文は1つにできると思います。 ・mono[num]は変数に値を代入して、それ以外の部分も添え字で配列を扱うよりもポインタに変えたほうが高速化できます。 根本的な問題の件は、gmp(GNU Multi Precision - 任意精度数演算ライブラリ)を使えば解決できると思えますが、自力で調べて導入する必要があります。 http://www001.upp.so-net.ne.jp/tklab/linux/sci1a.html windowsでの導入方法。 http://taylor.gotdns.org/gmp.html

共感・感謝の気持ちを伝えよう!

質問者からのお礼

> gotoが多すぎます。if文の工夫やforループのcontinue文の導入で、全部のgoto文を一掃できます。 WHENSAME と PRINT は消せました。 ただ、あと一つのgoto OUT; の消し方が思いつきませんでした…。 何か良い方法があれば教えてください。 > 高速化のためにはループを減らしてください。下3つのfor文は1つにできると思います。 num=0; for( m=1; m<len; m++){   if( mono[m]!=mono[0] && num==0)     num=m;   if( mono[m]!=mono[0] && mono[m]!=mono[num] || mono[m]==0)     goto OUT; } なんとか一つにまとめる事ができました。 これから気を付けていこうと思います。 > mono[num]は変数に値を代入して、それ以外の部分も添え字で配列を扱うよりもポインタに変えたほうが高速化できます。 ポインタはまだどういうものなのか調べただけで使った事がないので、できるかどうかわかりませんが…、色々試してみようかと思います^^ > 任意精度数演算ライブラリ こういうものもあるんですね。 小さい桁数をマスターできたら導入してみようかと思います。 ありがとうございました。

  • 回答No.1

>x=i*i;              //二乗 まずこれが破綻しています。 doubleは10進数で考えると有効桁数がせいぜい15桁の精度です。 10000000000.0 * 10000000000.0は有効桁数を確実にオーバーしていますよね? m=(int)i; これも環境にもよりますが通常intは32bitです。 (少なくともVC++2005では64bit用コンパイルであってもintは32bit) signedで-2,147,483,648~2,147,483,647 unsignedで0~4,294,967,295 ですので10000000000.0はint(32bit)には収まりません。 今回の場合だと64bit型のunsigned 整数型(0~18,446,744,073,709,551,615)を明示的に使うか それより大きな桁数の数値を扱う場合は 多倍長演算を考慮しなければなりません。 実装方法は色々とありますが、まずこの部分を考慮した プログラムを実装する必要があると思います。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

> 64bit型のunsigned 整数型(0~18,446,744,073,709,551,615)を明示的に使う 調べてみましたが、unsined long long int の事でしょうか? どのように使えばいいのかわからないのですが…教えていただけると助かります。 普通にint等と同じように使おうとするとエラーが出てしまって…;; 多倍長演算は、とりあえずそれ以下の桁数を使いこなせるようになってから詳しく調べてみようかと思います^^ 回答ありがとうございました。

関連するQ&A

  • プログラムの改良

    文章を単語毎に分割するプログラムを作っています。 下記のプログラムだと I□am□a□boy. の場合、Iとamとaとboyと.に分割され、ここまではいいのですが。 さらにI□am□□a□□□boy□.とスペースが余計に入ってしまってる文章の場合に、Iとamと□aと□□boyと□. と表示させたいのですがどう改良したらいいのか分かりません。 下記のプログラムだとI□am□□a□□□boy□.はIとamとaとboyと.になってしまいます。 どなたかプログラムの追加を教えていただけないでしょうか。□はスペース一個を表しております。 #include <stdio.h> int main() { int i,key,len,num ; char str[256],*ptr[128] ; num = 0 ; len = 0 ; ptr[0] = str ; do { key = getchar(); str[len] = (char)key ; if ( key == ' ' || key == '.' || key == ',' || key == '!' || key == '?' || key == '"' || key == 0x0a || key == 0x0d ){ str[len] = '\0' ; if ( str+len-ptr[num] ){ num ++ ; } ptr[num] = str+len+1 ; if( key=='.' || key== '!' || key=='?' || key=='"'){ str[++len]=(char)key; str[++len]='\0'; ptr[++num]=&str[len+1]; } } len ++ ; } while ( key != 0x0a && key != 0x0d && len < 255 ); str[255] = '\0' ; for (i=0 ;i<num ;i++){ printf("%d. %s\n",i+1,ptr[i]); } return i ; }

  • C言語 逆順の配列の仕方を教えてください

    今、大学でC言語の課題をやっています。サンプルが与えられています。 その課題は、配列の逆順です。 for文を使って、実行結果は以下のようにならなければならなく、「並び替えの結果は再び num1, num2 に保存される」という条件なのですが、逆順になるにはどのようなプログラムを組めば良いのでしょうか? ソースの「 /* ここに処理を書く */」にプログラムを書かなければいけないのですが、まったくの初心者でわかりません。誠にお手数ですが、教えていただければ幸いです。宜しくお願いいたします。 -----実行結果----- C:\c_lang>reverse --- before --- 2 4 9 10 5 3 1 7 8 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- after --- 6 8 7 1 3 5 10 9 4 2 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 -----以下ソース----- #include <stdio.h> void print_num( int *num, int len ); void reverse_num( int *num, int len ); int main( void ) { int num1[10]={2,4,9,10,5,3,1,7,8,6}; int num2[15]={1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15}; printf("--- before ---\n"); print_num( num1, 10 ); print_num( num2, 15 ); /* 逆順に並べ替え */ reverse_num( num1, 10 ); reverse_num( num2, 15 ); printf("--- after ---\n"); print_num( num1, 10 ); print_num( num2, 15 ); return 0; } void print_num( int *num, int len ) { int i; for( i=0; i<len; i++ ){ printf( "%d ", num[i] ); } printf("\n"); } void reverse_num( int *num, int len ) { /* ここに処理を書く */ } -----ソースここまで-----

  • Java for文 だけで逆ピラミッドを作る

    教えてください。 for 文だけで逆ピラミッドを作りたいのですが、*の数が2個ずつ減ればピラミッド 作成なのですが、私の文だと*は1個ずつしか減りません。 2個の指定はどのうように記述すればよいでしょうか? *を3と指定した場合 ***** (5) -***   (3) --*     (1) と表示したいのですが、下の文だと ***** (5) -****  (4) --***   (3) となってしまいます。 import java.io.*; class Sample4 { public static void main(String [] args) throws IOException { System.out.println("いくつ*を入力しますか?"); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); int num = Integer.parseInt(str); int j =0; int i =0; int s =0; //行数制御 for(i=0; i<num; i++) { for(s=0; s<i; s++) { System.out.print("-"); } for(j=num*2-1; j>i; j--) { System.out.print("*"); //System.out.print("d"); } //改行タグ System.out.print("\n"); } } }

  • 空白文字について

    C言語の初心者です。 今、VC 6.0の環境で電卓を作っています。 エディットボックスに数値を入力して計算させるプログラムなのですが エディットボックスにスペースを入力されても計算出来るようにしたいのですが解りません。 NULL文字をチェックすればよいのか、それとも「isspece」の関数を使って空白文字を調べればよいか解りません。プラス「+」、マイナス「-」の符合が入力されても計算出来るようには行えたのですが、どうしても空白(スペース)を入力された場合が、うまくいきません。 作成途中のソースコードです。ご指導お願いします。 // OnButton1() ///////////////////////////////////////////////////////////////////// void CKasanDlg::OnButton1() { adding(); char num1[128],num3[128]; int i,length=strlen(&num1[0]); int numk,numl=0; m_num3.GetLine( 0, num3 ); numk = sscanf( num3, "%d", &numl ); for( i=0; i<length; i++ ){ isdigit( (int) num1[i] ); } if(( numk == -1 )){ MessageBox("数値を入力してください。"); // メッセージボックス } } // 足算 (num) ///////////////////////////////////////////////////////////////// void CKasanDlg::adding() { char num1[128],num2[128]; int number1=0, number2=0,sum=0; CString ans; int nums,numa; int i=0, m=0, add1=0,add2=0; m_num3.SetSel( 0,-1 ); m_num3.Clear(); m_num1.GetLine( 0, num1 ); int length1 ; if(( num1[ 0 ] == '-' ) || ( num1[ 0 ] == '+' )){ length1 = strlen ( &num1[1] ); for( i=0; i<length1; i++ ){ add1 = isdigit( (int)num1[i+1] ); if( add1 == 0 ){ MessageBox("10進数字以外の値が入力されています。\n(足算・左側)"); break; } } } else{ length1 = strlen ( &num1[0] ); for( i=0; i<length1; i++ ){ add1 = isdigit( (int)num1[i] ); if( add1 == 0 ){ MessageBox("10進数字以外の値が入力されています。\n(足算・左側)"); break; } } } m_num2.GetLine( 0, num2 ); int length2; if(( num2[ 0 ] == '-' ) || ( num2[ 0 ] == '+' ) || ( num2[ 0 ] == ' ' )){ length2 = strlen ( &num2[1] ); for( m=0; m<length2; m++ ){ add2 = isdigit( (int)num2[m+1] ); if( add2 == 0 ){ MessageBox("10進数字以外の値が入力されています。\n(足算・右側)"); break; } } } else{ length2 = strlen (&num2[0]); for( m=0; m<length2; m++ ){ add2= isdigit((int)num2[m]); if( add2 == 0 ){ MessageBox("10進数字以外の値が入力されています。\n(足算・右側)"); break; } } } if((add1 == 0 ) && ( add2 == 0)){ return ; } if((add1 == 0 ) && ( add2 != 0)){ return ; } if((add1 != 0 ) && ( add2 == 0)){ return ; } nums = sscanf( num1, "%d", &number1 ); numa = sscanf( num2, "%d", &number2 ); if(( nums == 1) && ( numa == 1)){ sum = number1 + number2; ans.Format( "%d",sum ); m_num3.SetSel( 0, -1 ); m_num3.Clear(); m_num3.ReplaceSel( ans ); } } ///////////////////////////////////////////////////////////////////////////////

  • 数独のJavaプログラム

    数独の解答を一発で出すプログラムを考えています。 自分が考えたプログラムは下記の通りです。 import java.util.Random; public class NumberPlace { public static void main(String[] args) { int i, j, k, l, check=0, count=0, tmp; int a[][] = new int [9][9]; Random rnd = new Random(); int ran; for ( i=0; i<9; i++ ) for ( j=0; j<9; j++) a[i][j] = 0; count = 0; for ( i=0; i<9; i++ ) { for ( j=0; j<9; j++) { ran = rnd.nextInt(9); tmp = ran + 1; check = 0; for ( k=0; k<j; k++ ) if ( a[i][k] == tmp ) check = 1; for ( k=0; k<i; k++ ) if ( a[k][j] == tmp ) check = 1; for ( k=(i/3)*3; k<(i/3)*3+3; k++ ) for ( l=(j/3)*3; l<(j/3)*3+3; l++ ) if ( a[k][l] == tmp ) check = 1; if ( check == 0 ) a[i][j] = tmp; if ( check == 1 ) j--; if ( count > 50000 ) break; count++; } count = 0; } for ( i=0; i<9; i++) { for ( j=0; j<9; j++ ) { if ( a[i][j] < 10 ) { System.out.print(" "); } System.out.print(a[i][j]); } System.out.print("\n"); } } } これを実行すると、正しい数独の解が出来るまでに実行を20&#65374;30回。多い時は200回前後実行しないと出来ません。 実行結果(0は数独のルール上数字が入らない所) 9 3 6 5 4 1 7 8 2 1 7 4 2 9 6 5 3 0 5 2 8 7 3 0 0 0 0 2 1 5 3 7 8 4 6 9 8 6 3 4 1 9 2 7 5 4 9 7 6 5 2 1 0 0 7 5 1 8 6 4 9 2 3 3 8 2 9 0 0 0 0 0 6 4 9 1 2 5 8 0 0 これを一発で0がない状態にしたいのです。 因みにC言語だと下記のプログラムで一発で出るのですが。(前回質問したプログラム) int main(void) { int i,j,k,l,chk=0,num=0,tmp,count=0; int a[9][9];  srand((unsigned) time(NULL)); start: count=0; for(i = 0; i < 9; i++) for(j = 0; j < 9; j++) a[i][j]=0; for(tmp=1;tmp<10;tmp++){ num=0; while(num<9){ i = rand() % 9; j = rand() % 9; chk=0; for(k=0;k<9;k++) if(a[i][k]==tmp)chk=1; for(k=0;k<9;k++) if(a[k][j]==tmp)chk=1; for(k=(i/3)*3;k<(i/3)*3+3;k++){ for(l=(j/3)*3;l<(j/3)*3+3;l++){ if(a[k][l]==tmp)chk=1; } } if((chk==0)&&(a[i][j]==0)){ a[i][j]=tmp; num++; } if(count%100==99){ count++; for(i = 0; i < 9; i++) for(j = 0; j < 9; j++) if(a[i][j]==tmp)a[i][j]=0; num=0; } if(count>10000) goto start; count++; } } for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ printf("%d ",a[i][j]); } printf("\n"); } return 0; } このプログラムを実行すると一発で解答が出ます。 上のJavaプログラムを下のプログラムのようにするにはどうしたら良いでしょうか。

    • ベストアンサー
    • Java
  • java for文だけで逆ピラミッドを作成する

    Javaの勉強中です。 for文だけで、逆ピラミッドをだしたいのですが、なかなかうまくいきません。 どなたか教えてくださいませ。 まず、整数キーボドから入力します。整数を”段”を表示すると考えて作っています。 そして、さらに、逆ピラミッド(*)を表示するのがゴールです。 私が書いたプログラムです↓ import java.io.*; class Sample4 { public static void main(String [] args) throws IOException { System.out.println("*をの数を入力ししてください"); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); int num = Integer.parseInt(str); int j =0; int i =0; int s =0; //行数制御 for(i=0; i<num; i++) { for(s=0; s<i; s++) { System.out.print("-"); } for(j=0; j<num*2-1; j++) { System.out.print("*"); } //改行タグ System.out.print("\n"); } } } これだと、例えば整数を”7” とした時に下のように”-”は1個ずつ減り いい感じなのですが、”*”が2個ずつ減らないと逆ピラミッドになりません。 num -= -2; と*が2個ずつ入れる式を入れてみたのですが、意図した結果がでず・・ 数日悩んでおります。 1段目:************* 2段目:-************* 3 段目:--************* 4 段目:---************* 5 段目:----************* 6 段目:-----************* 7 段目:-------*************

  • ループが無駄に複雑な気が…

    以下は私が作成したプログラムで、 1.form[4][4][4]の三次元配列に0&#65374;32のランダムな正の整数を入れる 2.このランダムな数値の同じものは2つまで 3.form[i][j][0]&#65374;form[i][j][3]には同じ数値が入ってはいけない という条件を考えて作成したのですが、無駄に複雑になった気がします。 このプログラムはform[i][j][0]&#65374;form[i][j][3]が入らないように、数値が被ったら最初からやり直しにしています。 この作り方だと、これ入れないと最後の1個が被ってしまうものだったら無限ループが起きてしまうので…。 この無駄に複雑になってしまった気がするプログラムを、もっとシンプルに出来ないでしょうか? import java.util.Random; public class Loop { public static void main(String[] args){ int num; int[] check=new int [32]; int[][][] form=new int[4][4][4]; Random rand=new Random(); int i=0,j=0,k=0; for(i=0;i<32;i++) check[i]=0; i=-1; while(true){ while(true){ while(i<3){ num=rand.nextInt(32); if(check[num]!=2){ i++; form[i][j][k]=num; System.out.println(i+" "+j+" "+k+" "+form[i][j][k]); check[num]++; if(0<k){ for(int l=0;l<k;l++){ if(form[i][j][k]==form[i][j][l]){//同じだったらループのやり直し for(int m=0;m<32;m++) check[m]=0; i=-1; j=0; k=0; } } } } } if(j==3) break; num=rand.nextInt(32); if(check[num]!=2){ i=0; j++; form[i][j][k]=num; System.out.println(i+" "+j+" "+k+" "+form[i][j][k]); check[num]++; } } if(k==3) break; num=rand.nextInt(32); if(check[num]!=2){ i=0; j=0; k++; form[i][j][k]=num; System.out.println(i+" "+j+" "+k+" "+form[i][j][k]); check[num]++; } } for(i=0;i<4;i++){ for(j=0;j<4;j++){ for(k=0;k<4;k++){ System.out.println(k+" "+j+" "+i+" "+form[k][j][i]); } } } System.out.println("end"); System.exit(0); } }

    • ベストアンサー
    • Java
  • Double.parseDoubleの使い方

    Java初心者です。 以下のブログラムをコマンドライン引数が実数の場合に処理できるよう にしたいのですが、うまくいきません。どうしたらいいでしょうか? 申し訳ありませんが、ご回答、よろしくお願いいたします。 public class Narabikae { public static void main(String[] args) { int i = 0, j = 0, k = 0; double[] num = new int[args.length]; for(i = 0; i < args.length; i++) { double num[i] = Double.parseDouble(args[i]); } if (0 < args.length) { for(j = 0; j < args.length-1; j++) { for(i = j + 1; i < args.length; i++ ) { if(num[j] > num[i]) { k = num[j]; num[j] = num[i]; num[i] = k; } } } for(i = 0; i < args.length; i++) { System.out.print(num[i]); if (i != args.length-1) { System.out.print(" ⇒ "); } } } else { System.out.println("並び替えできません。"); } } }

    • ベストアンサー
    • Java
  • Java for文

    for文について、キーボードで入力して、その数が素数(1またはその数以外で割り切れない数)であるかを判断するコードですが、for文とif文の関係が良くわかりません。ご教示ください。 <サンプル> public static void main(String[] args) throws IOException{ System.out.println("2以上の整数を入力してください。"); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); int num = Integer.parseInt(str); ※1 for(int i=2; i<=num; i++){ if(i == num){ System.out.println(num + "は素数です。"); ※2 }else if(num % i == 0){ System.out.println(num + "は素数ではありません。"); break; ※1と※2の処理について初心者でもわかるような解説をおねがいできますでしょうか? よろしくお願いいたします。

  • POJ 2718

    #include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; int numbers[10]; int length; int n; int permutation(int num[10]){ int i; int oneco=0; for(i=0;i<length;i++){ if(num[i]){oneco++;} } int length2 = length-oneco; if((oneco==length)||(oneco==0)){return 1000000000;} if(abs(length2-oneco)>=2){return 1000000000;} vector<int> one; vector<int> two; for(int i=0;i<length;i++){ if(num[i]){one.push_back(numbers[i]);} else{two.push_back(numbers[i]);} } int len1 = one.size(); int len2 = two.size(); //cout << len1 << len2 << endl; // int num1[10];int num2[10]; vector<int> num1; vector<int> num2; //cout << one[1] << one[2] << endl; int count1=0;int count2 = 0; sort(one.begin(),one.end()); sort(two.begin(),two.end()); do{ int num=0; for(int i=1;i<len1;i++){ int onei = one[i]; for(int i2=0;i2<i;i2++){ onei = onei*10; } num = num + onei; }//cout << num << endl; if(one[0]==0){num = num;} else {num = num + one[0];} num1.push_back(num); //cout << num << endl; count1++; }while(next_permutation(one.begin(),one.end())); do{ int num = 0; for(int i=1;i<len2;i++){ int twoi = two[i]; for(int i2 =0;i2<i;i2++){ twoi = twoi*10; } num = num + twoi; // cout << num << endl; }//cout << "here" << num << endl; if(two[0]==0){num = num;} else {//cout << num ; num = num + two[0]; //cout << " " << num << endl; } num2.push_back(num); //cout << "here" << num << endl; count2++; }while(next_permutation(two.begin(),two.end())); int ans = 1000000000; //cout << len2; int dummy1 = 1; for(int x=1;x<len1;x++){ dummy1 = dummy1*10; }//cout << dummy1; int dummy2 = 1; for(int x=1;x<len2;x++){//cout << dummy2<< endl; dummy2 = (dummy2)*10; //cout << dummy2<< endl; }//cout << dummy2; for(int i=0;i<count1;i++){//cout << num1[i] << dummy1 << endl; if((num1[i]%dummy1)==num1[i]){if(num1[i]!=0){continue;}} for(int i2=0;i2<count2;i2++){ if((num2[i2]%dummy2)==num2[i2]){if(num1[i]!=0){continue;}} ans = min(ans,abs(num1[i]-num2[i2])); } } return ans; } //int permutation(int i[10]){return 1;} int dfs(int i,int num[10]){ if(i==length) return permutation(num); num[i]=0; int ans1 = dfs(i+1,num); num[i]=1; int ans2 = dfs(i+1,num); return min(ans1,ans2); } int main(){ cin >> n; getchar(); for(int i=0;i<n;i++){ /*for(length=0;length<10;length++){ cin >> numbers[length]; char c = getchar(); if(c=='\n'){break;} }*/ string str; while(1){ char c = getchar(); if(c=='\n'){break;} str += c;} length = 0; for(int i2=0;i2<str.length();i2=i2+2){ numbers[length] = (int)str[i2]-'0'; length++; } // cout << length; int dummy[10] = {0,0,0,0,0,0,0,0,0,0}; cout << dfs(1,dummy) << endl; } } 上記のどこが間違っているか教えてください。POJの2718です。書いてあるテストは通りました。