私はプログラミングチャレンジブックから最初の問題をコーディングしようとしています。このコードは、aからbまでに生成された数値の数を計算します。
新しいnは、nが偶数の場合はn / 2であり、奇数の場合は3 * n + 1
です。たとえば22の場合、数値は22 11 34 17 52 26 13 40 20 10 5 16 8 421と計算されます。数字の数は16です。113383を印刷するとコードが停止します。11000000として入力しました
。
#include <iostream>
#include <map>
#include <vector>
using std::cout;
using std::cin;
using std::string;
using std::endl;
using std::vector;
using std::map;
map<long,long> solution;
long sequences(long n) {
// returns the number of numbers(including 1) `n`produces till it becomes 1
if(n==1)
return 1;
else{
// assuming n>1
if(solution.find(n)!=solution.end())
return solution.find(n)->second;
long size = 0;
while(n!=1){
if(n%2==0){
n = n/2;
if(solution.find(n)!=solution.end())
return solution.find(n)->second + size;
}
else{
n = 3*n+1;
}
size++;
}
return size+1;
}
}
long sequences(long a,long b){
// returns the maximum numbers produced by numbers from a to b inclusive
long result,max = -1;
if(a<b){
for(long i=a;i<=b;i=i+1){
if(solution.find(i) == solution.end()){
cout<< i << endl;
result = sequences(i);
solution.insert(map<long,long>::value_type(i,result));
}
else{
//i present in solution
result = solution.find(i)->second;
}
if(result>max)
max = result;
}
return max;
}
return -1;
}
int main(int argc, char* argv[]) {
long a,b,max;
cin >> a >> b;
// while(cin>>a>>b){
cout<<a<<" "<<b<<" "<<sequences(a,b)<<endl;
/*}*/
return 0;
}