2009年03月15日

[パズル]パワーアップの問題

  
問題
ある任意のxに対して、xのn乗を求めたいとします。
演算としては乗算しかできないものとします。
このとき、最小の乗算回数で求めたいのですが、この
回数を 関数M(n)で表すことにします。
このM(n)を求めるプログラムを書いてください。
なお、一度計算した値は、覚えておいてかまいません。
M(23) と M(127)の値を求めてください。

たとえば、
M(2) は、1回です。これは x * xで求まるから自明ですね。
M(3) は、2回です。(x * x) * x
M(4) は、これも2回です。まず、(x * x) を求めれて、これを w とすれば、 w * w で求まるので、2回の掛け算で 4 乗が求まることになります。

----
この問題、解説にも書いてあるとおり、計算式を求めようとしてもその計算式を導き出すのは難しそうです。

で、この問題をよくよく吟味すると、問題にはn乗とありますが、xのn乗を求める必要は無いことに気がつきます。
必要なのは足し算だということがわかります。

例えば、M(9)で考えてみます。
すでに計算済みの値を F(z) と表します。F(3) は、xを3乗した値です。

どのような掛算で xの6乗になるかですが、最悪の計算は、
(x * x) * x * x * x * x * x * x * x で、8回の乗算が必要です。一度も計算済みの値を利用していません。
最小のだと、
((x * x) * x) * F(3) * F(3)
で、4回で求められます。
あるいは、同じ4回でも、
(x * x) * F(2) * F(4) * X
という求め方もあります。
その中間として、
((x * x) * x) * F(3) * F(2) * X
という計算方法もあります。この場合は、5回の計算結果となります。
つまり、M(9) = 4 です。

計算途中で何乗まで求めたかを表す数列で表すと、上の4つは、
2,3,4,5,6,7,8,9
2,3,6,9
2,4,8,9
2,3,6,8,9
となります。

ここからわかることは、9にたどりつく組み合わせを調べ、一番短い値を探せばよいことがわかります。
M(23)ならば、23に辿り着く数列を列挙し、その一番短いものを答えとすればよいのです。

結局、今まで解いてきたパズルと同様に、バックトラッキング手法を使い、しらみつぶしに調べて行くことにします。

何も考えずに書いたら、M(127)を求めるのにものすごく時間がかかってしまいました。
いろいろと工夫(枝刈りなど)をして、ようやく満足できるものができました。
以下、C#で書いた最終コードです。


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

namespace PowerUp {
class Program {
static void Main(string[] args) {
Stopwatch sw = new Stopwatch();
sw.Start();
Solver s = new Solver();
s.Found += new Action<List<int>>(s_Found);
int r = s.M(127);
Console.WriteLine("答え={0}回 (発見されたパターン={1})", r, count);
sw.Stop();
Console.WriteLine(sw.Elapsed);
}
static private int count = 0;

static void s_Found(List<int> list) {
count++;
list.ToList().ForEach(n => Console.Write("{0} ", n));
Console.WriteLine(": {0}回の乗算", list.Count - 1);
}
}

class Solver {
public event Action<List<int>> Found;
private List<int> _list = new List<int>(20);
private int _num;
private int _min;
public int M(int n) {
_num = n;
_min = int.MaxValue;
_list.Add(1);
Solve(1);
return _min - 1;
}

private void Solve(int n) {
if (n > _num)
return;
if (n == _num) {
if (_list.Count < _min) {
_min = _list.Count;
Found(_list);
}
return;
}

var q = from a in _list.Reverse<int>()
from b in _list.Reverse<int>()
select new Tuple { A = a, B = b };
foreach (var x in q.Distinct(new MyComparer()).ToList()) {
int c = x.A + x.B;
if (_list.ElementAt(_list.Count - 1) < c && !_list.Contains(c)) {
if (_list.Count + 1 < _min) {
_list.Add(c);
Solve(c);
_list.RemoveAt(_list.Count - 1);
}
}
}
}
}

class MyComparer : IEqualityComparer<Tuple> {
public bool Equals(Tuple x, Tuple y) {
return (x.A + x.B == y.A + y.B);
}

public int GetHashCode(Tuple obj) {
return (obj.A + obj.B).GetHashCode();
}
}

class Tuple {
public int A { get; set; }
public int B { get; set; }
}

}



 

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