1

我想打印（或以类似下面的人类可读格式发送到文件）任意大小的方表，其中每个表格单元格包含解决欧几里德算法所需的步骤数，以解决行/列标题中的两个整数，如这个（手写的表格，但我认为数字都是正确的）：

  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 步算法。

请参阅此内容以及求解欧几里得算法所需的步骤数我所追求的图形表示，但我想知道图像未显示的任何两个整数的实际步数。

我有算法（可能有更好的实现，但我认为这些可行）：

计步器：

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 新手，不知道编写表格的最佳方法（或任何方法）。我不需要特殊的格式，比如从表格单元格中偏移行/列头，因为我可以通过肉眼做到这一点，但只是让所有内容对齐以便我可以轻松阅读它对我来说太难了目前的技能水平，恐怕。我认为在两个嵌套的 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 回答