• ベストアンサー

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

趣味で最近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; }

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

  • ベストアンサー
  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答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 型など)で処理するように書き換えてみて下さい。

aniline
質問者

お礼

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

その他の回答 (9)

  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答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; } 以上。

aniline
質問者

お礼

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

aniline
質問者

補足

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

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

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

aniline
質問者

お礼

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

  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答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秒 -- 終了 --

aniline
質問者

お礼

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

  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答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 );  として文字列に変換すればよい。   ・以上。いろいろと試すか、コンパイラを変えるように。

aniline
質問者

お礼

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

  • Oh-Orange
  • ベストアンサー率63% (854/1345)
回答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; } 以上。

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

回答 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; }

aniline
質問者

お礼

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

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

気分転換に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); }

aniline
質問者

お礼

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

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

プログラムの問題点がいくつかあるので上げます。 ・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

aniline
質問者

お礼

> 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]は変数に値を代入して、それ以外の部分も添え字で配列を扱うよりもポインタに変えたほうが高速化できます。 ポインタはまだどういうものなのか調べただけで使った事がないので、できるかどうかわかりませんが…、色々試してみようかと思います^^ > 任意精度数演算ライブラリ こういうものもあるんですね。 小さい桁数をマスターできたら導入してみようかと思います。 ありがとうございました。

  • sha-girl
  • ベストアンサー率52% (430/816)
回答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)を明示的に使うか それより大きな桁数の数値を扱う場合は 多倍長演算を考慮しなければなりません。 実装方法は色々とありますが、まずこの部分を考慮した プログラムを実装する必要があると思います。

aniline
質問者

お礼

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

関連する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; }

  • 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です。書いてあるテストは通りました。

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

    この単語分割プログラムを区切り文字である( . ? ! " )等も一つの単語として表示させたいのですが、どう改良したらいいかわかりません。 どなたかプログラムの追加削除を教えていたたけないでしょうか。 #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さんのプログラムを引用しました。

  • プログラムの改良

    文章を単語毎に分割するプログラムを作っています。 下記のプログラムだと 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 ; }

  • for文&if文を使った問題について教えてください。

    参考書の練習問題を解いていて、応用力がないのか理解できない ので、分かる方教えていただけませんか? 問題: キーボードから整数を入力させ、その数が素数であるかどうかを 判断するコードを記述してください。 解答: import java.io.*; class SampleP5 { 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); for(int i=2; i<=num; i++){ if(i = = num){ System.out.println(num + "は素数です。"); } else if(num % i = = 0){ System.out.println(num + "は素数ではありません。"); break; } } } } 例えば"7"を入力すると「7は素数です」と出力されるようなんですが、 『i = 7』だとして、『 if(i = = num)』の条件って当てはまるん ですか?for文でiの初期値が2だから、『2 = = 7』で当てはまらない と思うんですが・・・ 考え方が間違っているんですかね? ※ちなみに(= =)のところ、実際はスペース空いてません。  ここの画面での表示上くっついて1本の線になってしまうので、  スペースを空けて入力したまでです。

    • ベストアンサー
    • Java
  • 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言語 逆順の配列の仕方を教えてください

    今、大学で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 ) { /* ここに処理を書く */ } -----ソースここまで-----

  • このプログラムの問題点を教えてください。

    //数独 #include <iostream.h> const int num_Max = 100; //一辺のマス最高値 void input_data( int a, int [num_Max][num_Max] ); //入力関数 void yoko_data( int a, const int [100][100], int & ); //判定 void tate_data( int a, const int [100][100], int & ); void block_data( int a, int b, const int [100][100], int & ); main() { int num; //一辺のマスの数 int m; //一ブロックの一辺にあるマスの数 int okey; //numが正常か判別 int dx, dy, dz; int masu[num_Max][num_Max]; //全部のマス cout << "\n埋められた数独が正しいかどうか判断するプログラムです。\n"; while(1){ cout << "横何マスありますか? (4-100)>>" ; cin >> num ; if( num > num_Max || num < 4){ cout <<"範囲外です。再入力して下さい。" ; }else{ m = sqrt( num ); okey = num - m * m; if(okey != 0) cout << "その数字は数独として成り立ちません。再入力して下さい。"; } } //マスの入力 input_data( num, masu ); //横判定 yoko_data( num, masu, dx ); if(dx = 0){ //縦判定 tate_data( num, masu, dy ); if(dy = 0){ //マス判定 block_data( num, m, masu, dz ); } } if(dx == dy == dz == 0) cout <<"\n大正解♪ おめでっとー。\n"; return 0; } //入力 void input_data( int kazu, const int matrix[num_Max][num_Max]) { cout <<"\nマスの数字の入力を左上から順に、右へと行って下さい。"; for(int i = 0; i < kazu; i++){ for(int j = 0; j < kazu; j++){ cout << i+1 << "行目の" << j+1 << "列目 >>"; cin >> matrix[i][j] ; } } } //横列(行)を順に判定 void yoko_hantei( int kazu, int matrix[num_Max][num_Max]) { int kaburi; //かぶっているか判定する用 int vx = 0; //かぶっていたと判定されたかどうかを見る用 for(int i = 0; i < kazu; i++){ //横一列取り出しました。 for(int j = 0; j < kazu; j++){ for( int k = 1; j+k < kazu; k++){ kaburi = matrix[i][j] - matrix[i][j+k]; if(kaburi == 0){ //かぶってたらループから抜け出す vx++; break; } } } } if(vx > 0) cout << "\n横列(行)検索時に不適切な部分を発見しました。\n"; return vx; } //縦列(列)を順に判定 void tate_hantei( int kazu, int matrix[num_Max][num_Max]) { int kaburi; //かぶっているか判定する用 int vy = 0; //かぶっていたと判定されたかどうかを見る用 for(int j = 0; j < kazu; j++){ //縦一列取り出しました。 for(int i = 0; i < kazu; i++){ for( int k = 1; k < kazu-1; k++){ kaburi = matrix[i][j] - matrix[i+k][j]; if(kaburi == 0){ //かぶってたらループから抜け出す vy++; break; } } } } if(vy > 0) cout << "\n縦列(列)検索時に不適切な部分を発見しました。\n"; return vy; } //1ブロックごとに判定 void block_data( int kazu, int ruto, int matrix[num_Max][num_Max]) { int hantei[num_Max][num_Max] ; //判定する部分を切り出す用 int kaburi; int vz; //まずブロックごとに切り出してみる for(int i = 0; i < ruto-1; i++){ for(int j = 0; j < ruto-1; j++){ int h = 0; //何ブロック目か int g = 0; //そのブロックの何個目か (h-1)++; for(int l = 0; l < ruto-1; l++){ for(int k = 0; k < ruto-1; k++){ hantei[h][g++] = matrix[i * m + k][j * m + l]; } } } } //かぶっているか判定する for(int x = 0; x < kazu; x++){ for(int y = 0; y < kazu; y++){ for( int z = 1; z < kazu-1; z++){ kaburi = hantei[x][y] - matrix[x+z][y]; if(kaburi == 0){ //かぶってたらループから抜け出す vz++; break; } } } } return vz; } C++で作成したものです。 コンパイルエラーが出てしまうのですが、原因を教えていただけませんか?