-2

これは、間違った答えを出している 3n+1 問題に対する私の解決策です。私は過去 5 日間以来、この 1 つの静かさに何度も苦労してきました。私のソリューションの問題を理解するのを手伝ってください。私は末尾再帰を使用し、マップを保存して 2​​ のべき乗を追跡し、より迅速に答えに到達できるようにしています。問題へのリンクはProgramming Challenges - The 3n + 1 problemです

#include <stdio.h>
#include <map>
using namespace std;

#define MAX 1000000
typedef long long int ll;
map<int, int> globalMap;

void process(){
  ll i = 1, key = 1, value = 1;
  while(value < MAX){
    globalMap[value] = key;
    key++; value *= 2;
  }
  return;
}

ll cycleLength(ll n, ll ans){
  if(n == 1) return ans; 
  if(globalMap.find(n) != globalMap.end()) return ans+globalMap[n];
  else{
    if(n%2){
      return cycleLength(3*n+1, ++ans);
    }
    else return cycleLength(n/2, ++ans);
  }
}
int main(){
  ll i, j, temp, max=-1;
  process();
  while(scanf("%lld%lld", &i, &j) != EOF){
    max = -1;
    for(ll a = i; a <= j; ++a){
      temp = cycleLength(a, 0);
      if(max < temp) max = temp;
    }
    printf("%lld %lld %lld\n", i, j, max);
  }
  return 0;
}
4

2 に答える 2

2

関数は 1 のサイクル長が 1 にprocess()なるように入力しますが、およびに渡された場合、関数はサイクル長 0 を返します。globalmapcyclelengthll = 1ans = 0

したがって、次の入力で：

1 1

1 2

あなたのプログラムは以下を出力します:

1 1 0
1 2 2

これはあなたのsol'nの難点かもしれません。

于 2014-02-22T12:34:57.203 に答える
1

i>j の場合、ソリューションは機能しません。

代わりに、i,j の最小値から i,j の最大値まで繰り返してみてください。

i と j は元の順序で出力する必要があることに注意してください。したがって、順序が間違っている場合に i と j を入れ替えないでください。

于 2014-02-22T11:38:14.120 に答える