1

任意のサイズの正方形のテーブルを印刷（または以下のような人間が読める形式でファイルに送信）したいのですが、各テーブルセルには、次のような行/列の見出しの2つの整数に対するユークリッドのアルゴリズムを解くために必要なステップ数が含まれています。これ（表は手書きですが、数字はすべて正しいと思います）：

  1  2  3  4  5  6
1 1  1  1  1  1  1 
2 1  1  2  1  2  1
3 1  2  1  2  3  1
4 1  1  2  1  2  2
5 1  2  3  2  1  2
6 1  1  1  2  2  1

スクリプトを使用すると、理想的には、開始整数（1は上または11は下またはその他の任意のもの）と終了整数（6は上または16は下またはその他の任意で開始整数より大きい）を選択できます。これも行うことができます：

   11 12 13 14 15 16
11  1  2  3  4  4  3
12  2  1  2  2  2  2
13  3  2  1  2  3  3
14  4  2  2  1  2  2
15  4  2  3  2  1  2
16  3  2  3  2  2  1

テーブルは対角線に対して対称であるため、テーブルの半分だけに一意の情報が含まれ、対角線自体は常に1ステップのアルゴリズムであることがわかります。

これと私が求めているもののグラフ表示については、これを参照してくださいユークリッドのアルゴリズムを解くために必要なステップ数。ただし、画像に表示されていない2つの整数の実際のステップ数を知りたいです。

私はアルゴリズムを持っています（おそらくより良い実装がありますが、これらはうまくいくと思います）：

ステップカウンター：

def gcd(a,b):
    """Step counter."""
    if b > a:
        x = a
        a = b
        b = x
    counter = 0
    while b:
        c = a % b
        a = b
        b = c
        counter += 1
    return counter

リストビルダー：

def gcd_steps(n):
    """List builder."""
    print("Table of size", n - 1, "x", n - 1)
    list_of_steps = []
    for i in range(1, n):
        for j in range(1, n):
            list_of_steps.append(gcd(i,j))
    print(list_of_steps)
    return list_of_steps

しかし、私はテーブルの書き方に完全に夢中になっています。私はiとjなどを含む二重ネストされたforループについて考えましたが、Pythonは初めてであり、テーブルを作成するための最良の方法（または任意の方法）についての手がかりがありません。目で確認できるように、テーブルセルから行/列の見出しをオフセットするような特別な書式設定は必要ありませんが、すべてを並べて簡単に読み取れるようにするだけでは、私には難しすぎます。現在のスキルレベル、私は恐れています。必要な数を計算しているので、ネストされた2つのforループ内で印刷/出力するのはおそらく理にかなっていると思います。そのため、リストビルダーにはいくつかの印刷ステートメントがあり、リストを返しますが、私はしません。私が求めていることを実行するために印刷魔法を働かせる方法を知っています。

4

1 に答える 1

1

これを試して。プログラムは、メモリ使用量を制限するために、データを行ごとに計算し、使用可能な場合は各行を出力します。

import sys, os

def gcd(a,b):
   k = 0
   if b > a:
      a, b = b, a
   while b > 0:
      a, b = b, a%b
      k += 1
   return k

def printgcd(name, a, b):
   f = open(name, "wt")
   s = ""
   for i in range(a, b + 1):
      s = "{}\t{}".format(s, i)
   f.write("{}\n".format(s))
   for i in range(a, b + 1):
      s = "{}".format(i)
      for j in range (a, b + 1):
         s = "{}\t{}".format(s, gcd(i, j))
      f.write("{}\n".format(s))
   f.close()

printgcd("gcd-1-6.txt", 1, 6)

上記は、意図的に破棄されているため、すべての計算値を含むリストを返しません。ただし、これは簡単です。これがハッシュテーブルを使った解決策です

def printgcd2(name, a, b):
   f = open(name, "wt")
   s = ""
   h = { }
   for i in range(a, b + 1):
      s = "{}\t{}".format(s, i)
   f.write("{}\n".format(s))
   for i in range(a, b + 1):
      s = "{}".format(i)
      for j in range (a, b + 1):
         k = gcd(i, j)
         s = "{}\t{}".format(s, k)
         h[i, j] = k
      f.write("{}\n".format(s))
   f.close()
   return h

そしてここにリストのリストがある別のものがあります

def printgcd3(name, a, b):
   f = open(name, "wt")
   s = ""
   u = [ ]
   for i in range(a, b + 1):
      s = "{}\t{}".format(s, i)
   f.write("{}\n".format(s))
   for i in range(a, b + 1):
      v = [ ]
      s = "{}".format(i)
      for j in range (a, b + 1):
         k = gcd(i, j)
         s = "{}\t{}".format(s, k)
         v.append(k)
      f.write("{}\n".format(s))
      u.append(v)
   f.close()
   return u
于 2013-01-24T09:13:49.117 に答える