2009年03月08日

[パズル]巡回数

  
問題
2倍して桁が巡回する最小の自然数nを求めてください。
例えば、1234の場合は、2倍した値が、2341, 3412, 4123 のいずれかになれば、巡回すると言えます。実際には、2468なので、巡回はしません。
また、途中に0が入っても良いことにします。
つまり、123の巡回として、2301, 23001も認めます。

---
力づくでやるのが、もっともお手軽な方法ですね。ただ、それだけだとつまらないので、配列やコレクションを使わないという制約をつけてみました。
こういった制約をつけてプログラミングするのも、頭の体操になって良いですね。

今回も、バカの一つ覚えのようにC#でLINQ使っています。

RoundedNumberクラスの、Roundsメソッドは、与えられた数の巡回する数を列挙するメソッドです。
このメソッドの中で、Rotateメソッドを呼び出し、ひとつ右にずらした値を求めています。

IsSimilarは、途中に0が入っても良いように、0を除外して比較を行っています。

Digitsメソッドは、与えられた数を一桁目から順に取り出すメソッドです。


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

namespace RoundNumber {
class Program {
static void Main(string[] args) {
RoundedNumber rn = new RoundedNumber();
foreach (var num in Enumerable.Range(1, int.MaxValue)) {
if (rn.IsRoundedNumber(num)) {
Console.WriteLine("{0}, {1}", num, num * 2);
break;
}
}
}
}

class RoundedNumber {
public bool IsRoundedNumber(int num) {
IEnumerable<int> dblnum = Digits(num * 2);
return (Rounds(num).Any(x => IsSimilar(dblnum, x)));
}

private IEnumerable<IEnumerable<int>> Rounds(int num) {
var digits = Digits(num);
IEnumerable<int> next = digits;
for (int i = 0; i < digits.Count()- 1; i++) {
next = Rotate(next);
yield return next;
}
}

private IEnumerable<int> Rotate(IEnumerable<int> buf) {
return buf.Skip(1).Concat(buf.Take(1));
}

private bool IsSimilar(IEnumerable<int> a, IEnumerable<int> b) {
return a.Where(c => c != '0').SequenceEqual(b.Where(c => c != '0'));
}

private IEnumerable<int> Digits(int num) {
while (num > 0) {
yield return num % 10;
num = num / 10;
}
}
}
}




この結果は、142857でした。
そのほかにも、2倍して巡回する数があるので、興味のある方は調べてみてください。3倍して巡回する数も求めてみると、びっくりすると思います。
数って面白いですね。

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


 

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