DouKaku? 4382 shinh: それなりに速く終わるやつを。手元で1秒切...(正しい文(クイズ))

Comment detail

それなりに速く終わるやつを。手元で1秒切ります。たぶん正しい気がするんですが自信は無いような。というかたぶんn=7以降は同じパターンで2種類しか解がない、と示せる気がします。

def x(b,a,n,e,z)
  if b==n
    if a==e
      puts (0...b).map{|i|"#{i.to_s(b)}*#{a[i].to_s(b)}"}*','
    end
  else
    1.upto(b<5?5:[n>1?[4-n,0].max+e[n]:99,b+2-z+n].min){|i|a[n]=i
      f=e.dup
      i.to_s(b).scan(/./){f[$&.to_i(b)]+=1}
      next if (0..n).any?{|j|f[j]>a[j]}
      x(b,a,n+1,f,z+i)}
  end
end
2.upto(16){|b|p b
  x(b,[0]*b,0,[1]*b,0)}

#4382を移植

const string ALNUM = "0123456789abcdefghijklmnopqrstuvwxyz";
static void Main(string[] args)
{
  for (int i = 2; i <= 16; i++)
  {
    Console.WriteLine(i);
    int[] a = new int[i];
    int[] b = new int[i];
    for (int j = 0; j < i; j++)
      b[j] = 1;
    x(i, a, 0, b, 0);
  }
  Console.ReadKey();
}

static void x(int b, int[] a, int n, int[] e, int z)
{
  if (b == n)
  {
    if (Eq(a, e))
    {
      for (int i = 0; i < b; i++)
      {
        if (i > 0) Console.Write(", ");
        Console.Write("{0}*{1}", ToS(i, b), ToS(a[i], b));
      }
      Console.WriteLine();
    }
  }
  else
  {
    int m = b < 5
      ? 5
      : new List<int> {
          n > 1
            ? new List<int> { 4 - n, 0 }.Max() + e[n]
            : 99,
          b + 2 - z + n
        }.Min();
    for (int i = 1; i <= m; i++)
    {
      a[n] = i;
      int[] f = e.Clone() as int[];
      foreach (char c in ToS(i, b))
      {
        f[ToI(c, b)]++;
      }
      if (Range(0, n).Any(j => f[j] > a[j])) continue;
      x(b, a, n + 1, f, z + i);
    }
  }
}
static bool Eq(int[] a, int[] b)
{
  if (a == null || b == null) return (a == b);
  if (a.Length != b.Length) return false;
  for (int i = 0; i < a.Length; i++)
    if (a[i] != b[i]) return false;
  return true;
}
static string ToS(int i, int b)
{
  char[] c = ALNUM.ToCharArray();
  var sb = new StringBuilder();
  for (; i > 0; i /= b) sb.Insert(0, c[i % b]);
  return sb.Length > 0 ? sb.ToString() : "0";
}
static int ToI(char c, int b)
{
  return ALNUM.IndexOf(c);
}
static IEnumerable<int> Range(int s, int e)
{
  for (int i = s; i <= e; i++) yield return i;
}

#4382をprototype.jsを用いて写経しました。
・申し訳ないんですが、IE6でしか動いてません。
　FireFox2では、new Array(b).map・・・の動きがいまいちです。
・かつ、ひじょ～に遅くなりました。

map、max、min、entries、anyがprototype.jsです。

see: prototype.js ver 1.6.0 リファレンス

<html>
<head>
<script type="text/javascript" src="../../prototype-1.6.0.2.js"></script>
<script type="text/javascript">
function x(b, a, n, e, z) {
    if(b == n) {
        if(a.toString() == e.toString())
            document.write(new Array(b).map(function(v, i){return i.toString(b)+'*'+a[i].toString(b);})+'<br />');
    } else {
        var m = b<5 ? 5 : [n>1 ? [4-n,0].max()+e[n] : 99, b+2-z+n].min();
        for(var i = 1; i <= m; i++) {
            a[n] = i;
            f = e.entries();
            i.toString(b).toArray().map(function(v){f[parseInt(v, b)]++;});
            if(new Array(n).any(function(v, j){return f[j] > a[j];})) continue;
            x(b, a, n+1, f, z+i);
        }
    }
}

for(var b = 2; b <= 16; b++) {
    document.write(b + '<br />');
    var a = new Array(b).map(function(v,i){return 0;}); // 要素数b・初期値0の配列
    var e = new Array(b).map(function(v,i){return 1;}); // 要素数b・初期値1の配列
    x(b, a, 0, e, 0);
}
</script>
</head>
<body>
</body>
</html>

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq