再帰を使って2進数の連続する1bitの最大値を求める関数
- 再帰を使って2進数の連続する1bitの最大値を求める関数について教えてください。
- 現在の関数では、最下位ビットのチェックと右シフトを使用して最大値を求めています。再帰を使って書き直す場合、どのようになるのか教えてください。
- サンプルコードを教えていただけると幸いです。
- ベストアンサー
再帰を使用した関数にしたい
以下は n を２進数としたときに、連続する 1bit の最大値を求める関数です。 最下位ビットチェックして右シフトでカウントしています。 これを再帰を使って書き直した場合、どんな感じになるでしょうか？ 宜しければ、サンプルコードを教えてください。 #include <algorithm> using namespace std; int getBitMaxWidth(long long n) { int count = 0; int max_count = 0; do { if (n & 1LL) { //最下位 bit チェック count++; max_count = max(count, max_count); } else { count = 0; } } while ( n>>=1 ); return max_count; }
- marudora
- お礼率100% (1/1)
- C・C++・C#
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
http://stackoverflow.com/a/12617595 の回答を再帰化すると、 https://pastebin.com/KcSFAeSp になるかなと思います。
関連するQ&A
- 再帰
他の質問と平行してしまい申し訳ありません。再帰について少々おききしたいのですが、 配列の中にある数字の中から最大値と最小値を再帰処理でもとめたいのですが、うまくいきません。 public int minMax(n, array, min, max){ // nは配列のサイズです。 min=max=array[n-1]; if(array[n-2]<min) min=array[n-2]; if(array[n-2]>max) max=array[n-2]; return minMax(n-1,array,min,max); ｝ 最初に比較するために min=max=array[n-1];と初期化したのですが、再帰処理ですからまた同じ初期化をしてしまうことになります。 forループなどを使えるなら初期化だけループの外でやれば済むのですが、再帰だとどのようにすればよいのでしょうか。 宜しくお願いいたします。
- 締切済み
- Java
- 素数 再帰関数
メイン #include<stdio.h> extern void count_primes(void); extern void print_primes(void); int max; int count; int primes[1000] int main(void) { printf("Uper limit: "); scanf("%d",&max); count_primes(); print_primes(); } 素数を求める（関数呼び出し） extern int nextprime(int n); extern int max; extern int count; extern int primes[]; void count_primes(void) { int i; count=0; for(i=2;i<=max;i=nextprime(i)){ primes[count++]=i; } リカーバシブ（次の素数） int nextprime[int n] { int i; for(;;){ n++; for(i=2;i*i<=n;i=nextprime(i)){ if(n%i==0) break; } if(i*i>n) break; } return n; } 素数プリント #include<stdio.h> extern int count; extern int primes[]; void print_primes(void) { int i for(i=0;i<count;i++){ if((i>0)&&(i%10==0) printf("\n"); printf(" %6d",primes[i]); } printf("\n素数の数 %d\n",count); } これら４つのモジュールで素数 nが求められますがアルゴリズム理解できません。この２つの関数のアルゴリズムについて、ご教授ください。め
- 締切済み
- C・C++・C#
- この文章正確ですか?
#include <string> #include <iostream> using namespace std; int main(){ string s1; s1 = "こんにちわ"; count << s1 << endl; } これをコンパイルしようとしてもできません。 どこが間違っているのでしょうか?
- ベストアンサー
- C・C++・C#
- 再帰関数を用いて配列の合計を求める
かなり(約三時間)悩んでまだ分からないので質問します。 再帰関数を用いて配列の中の数字(floatで定義されている)の合計を求めるプログラムを作っています。階乗を求めるプログラムの例を見ながらやっているのですがもう降参です。簡単だと思ったんですけど配列と組み合わせでもう頭がパニックです。どなたか答え(またはヒント)を教えてください。 よろしくお願いします。 なお、下のプログラムは私が1から作りましたので完全に間違っている可能性大です。参考にしないでください。(^^ゞ #include <iostream> using namespace std; float recur(int numF); int main() { int num; float sum; cout << "Enter an integer number: "; cin >> num; //再帰関数なんてこうやれば使わなくても出来るのに～! // for(i=0; i<num; i++) // sum += array[i]; sum = recur(num); cout << "The sum of all the numbers: " << sum << endl; return 0; } float recur(int numF) { int i; float array[numF]; //定数式が必要です、と怒られる for(i=0; i<numF; i++) return array[i] += array[i-1]; //ここに再帰の式が必要 }
- ベストアンサー
- C・C++・C#
- 関数の再帰処理
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657... という数列（フィボナ数列）を再帰処理でだしたいのですが・・・・・ include <stdio.h> int function( int ); int main( void ){ int n; do { printf( "0 以上の整数値を入力して下さい→ " ); scanf( "%d", &n ); }while ( n < 0 ); printf( "計算結果： %d\n", function( n ) ); getchar(); getchar(); return 0; } int function( int n ){ //フィボナの処理（function）の再帰呼び出しによる } function内に再帰処理を用いてprintf( "計算結果： %d\n", function( n ) );で画面出力したいのですが・・・・・・。
- ベストアンサー
- C・C++・C#
- プログラミング言語C++のエラー
#include <iostream> #include <string> using namespace std; template <typename T> T max(T n1, T n2) { if(n1 > n2) { return n1; } return n2; } int main(){ cout << max<int>(1,2) << endl; cout << max<double>(1.75,3.12) << endl; string s1 = "aiu",s2 = "eo"; cout << max<string>(s1,s2) << endl; return 0; } このコードを入力すると、添付写真のようなエラーが出ます。使用しているのはmacOSのVisual Studio codeです。明らかにいじってはいけない場所のファイル /Library/Developer/CommandLineTools/SDKs/MacOSX14.2.sdk/usr/include/c++/v1/__algorithm/max.h (添付写真のエラー表示下部のパス)が勝手に参照され、引数が一致してしまっているオーバーロードした関数となってしまいます。maxをMaxなどとすると問題は解決するのですが、既存のコードを編集する際、いちいちmaxでエラーが出ると不便です。 ちなみにテンプレートではなく、引数ごとに関数を作ればエラーは出ません。 解決方法を知っている方が居れば教えてほしいです。
- ベストアンサー
- C・C++・C#
- 関数呼び出しについて
今cygwin 上でC++の勉強をしているのですが 以下の2つのプログラムの違いがよくわかりません どなたかよろしくお願いします ＜プログラム１＞ #include<iostream> using namespace std; int a(); int main(){ cout << abs(); return 0;} int a(){ cout << "test\n"; return 1;} ＜プログラム２＞ #include<iostream> using namespace std; int a(int i); int main(){ cout << a(1); return 0;} int a(int i){ cout << "test\n"; return i;} プログラム１では関数a()内の"test"が出力されるのですが プログラム２ではa(int i)内の"test"は出力されません。 この違いはどこにあるのでしょうか？ 同じプログラムでint a() と int a(int i)を double a() と double a(double d)にすると この違いは生じません。なぜaの戻り値をint に設定したときだけ この違いが生じるのでしょうか？
- 締切済み
- C・C++・C#
- int型変数の簡潔なプログラム
#include<iostream> using namespace std; int main(void){ int max = a; int min = a; if(a > b){ min = b; }else{ max = b; } cout << "小さい方の値は" << min << "です。\n"; cout << "大きい方の値は" << max << "です。\n"; } これの、 int max = a; int min = a; と if(a > b){ min = b; }else{ max = b; } が解りません。 何故変数をaからbにチェンジしているのでしょうか 初心者なのでお手柔らかにお願いします。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- CygwinでSTLの勉強をしていますが・・・
今C++のSTLの勉強をしています。 本に載っているサンプルプログラムを打って実行しようとしたら エラーがでてしまいました。 エラーの内容はprintとtotalが見つかりませんというエラーです。 コンパイラはcygwinを使ってます。 よろしくお願いします。 /*for_each()アルゴリズム*/ #include<iostream> #include<algorithm> #include<vector> #include<functional> #include<> using namespace std; int main() { int n[]={100,200,300,400,500,600}; int size=sizeof n/sizeof(int),i; vector<int> v; for(i=0;i<size;++i) v.push_back(n[i]); for_each(v.begin(),v.end(),print<int>()); cout<<endl; cout<<(for_each(v.begin(),v.end(),total<int>())).gettotal()<<endl; return 0; }
- ベストアンサー
- C・C++・C#
お礼
サンプルコードありがとうございます。該当部分を抜き出してみました。 static uint8_t count_consecutive_ones_recursive_sub(uint64_t in, uint8_t acc) { if (in == 0) return acc; return count_consecutive_ones_recursive_sub((in & (in << 1)), acc + 1); } 再帰だと簡潔に書けますね。自分を呼び出した時、計算結果を引数で伝えていく感じでしょうか。 参考になりました。