2009年03月29日

[パズル]わなにはまるまで

  
問題
「桁切り2のべき乗和」という関数 f(x)を考えます。たとえば、234という数値を引数に渡すと、
f(234) = 2^2 + 2^3 + 2^4
= 4 + 8 + 16
= 28
※ ^はべき乗を表す

となります。
この関数を使い

f(a) -> f(f(a)) -> f(f(f(a))) -> f(f(f(f(a)))) -> ...

と求めて行くと、無限に発散するか、同じところに戻ってきてループするかのどちらかです。
例えば、a が 1 のときは、

1, 2, 4, 16, 66, 128, 262, 72, 132, 14, 18, 258, 292, 520, 37, 136, 74, 144, 34, 24, 20, 5, 32, 12, 6, 64, 80, 257, 164, 82, 260, 69, 576, 224, 24, ...

となり、ループに陥ります。

このとき、任意の数値 a(1..10000000)のなかで、最も早くループに陥るのはどの数かを求めてください。

---

この問題は、ループにならずに、発散してしまう場合があったらどうするのかとうことを考えなくてはいけません。

しかし、a = 1 のときにはループに陥ることが分かっているので、この回数より多いものはすべて除外する、というコードを加えれば、発散する場合があっても対応できることになります。

で、C#で書いたコードは、以下のとおりです。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1 {
class Program {
static void Main(string[] args) {
Solver sol = new Solver();
sol.Solve();
}
}

class Solver {
public int Solve() {
int ans = -1;
int maxloop = int.MaxValue;
foreach (var a in Enumerable.Range(1, 300)) {
SumPower s = new SumPower();
int f = s.SigmaF(a, maxloop);
if (f < maxloop) {
maxloop = f;
ans = a;
}
}
Console.WriteLine("{0} {1}",ans, maxloop);
SumPower sp = new SumPower();
sp.SigmaF(ans,int.MaxValue);
Console.WriteLine(sp);
return 1;
}

}
class SumPower {
private List<int> List = new List<int>();
public override string ToString() {
return string.Join(", ", List.Select(n => n.ToString()).ToArray());
}
public int F(int n) {
string s = n.ToString();
int f = 0;
foreach (var c in s) {
int i = int.Parse(c.ToString());
f += (int)Math.Pow(2, i);
}
return f;
}

public int SigmaF(int a, int maxloop) {
try {
List.Clear();
List.Add(a);
while (true) {
a = F(a);
if (List.Contains(a))
break;
List.Add(a);
if (maxloop < List.Count)
return int.MaxValue;
}
List.Add(a);


return List.Count - 1;
} finally {
;
//Console.WriteLine(this); debug用
}
}
}
}





結果は、148 でした。

148 -> 274 -> 148 -> ...

となって、なんと2回目には、ループに入ってしまいます。ということで、これ以上やっても、これ以上短い答えはありません。
そういう意味では、さらに実行時間を短くできますね。

※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51785009