图灵机欧几里得求最大公约数的算法 python
我的代码在底部：（如果有人有足够的耐心阅读全部内容，我会感到非常惊讶）
它输出了错误的数字，但我不知道为什么。我遵循了算法。输入必须是 2 个一元数字，例如 2 和 6 => 01101111110。如果有更简单的方法来编写此算法，请告诉我。这是算法（来自罗杰·彭罗斯的《皇帝的新思想》一书）
我的代码是：
x = input("Dos numeros en sistema unario separado por un 0: ")
x = list(x)
pos = 0
valorMaq = 0
while (True):
if valorMaq==0 and x[pos]=='0':
valorMaq=0
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==0 and x[pos]=='1':
valorMaq=11
x[pos]='0'
pos=pos-1
print(x)
elif valorMaq==1 and x[pos]=='0':
valorMaq=10
x[pos]='1'
pos=pos+1
print(x)
elif valorMaq==1 and x[pos]=='1':
valorMaq=1
x[pos]='1'
pos=pos-1
print(x)
############################################
elif valorMaq==10 and x[pos]=='0':
valorMaq=1010
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==10 and x[pos]=='1':
valorMaq=11
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==11 and x[pos]=='0':
valorMaq=100
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==11 and x[pos]=='1':
valorMaq=11
x[pos]='1'
pos=pos+1
print(x)
#############################################
elif valorMaq==100 and x[pos]=='0':
valorMaq=100
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==100 and x[pos]=='1':
valorMaq=101
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==101 and x[pos]=='0':
valorMaq=111
x[pos]='0'
pos=pos-1
print(x)
elif valorMaq==101 and x[pos]=='1':
valorMaq=110
x[pos]='1'
pos=pos-1
print(x)
elif valorMaq==110 and x[pos]=='0':
valorMaq=110
x[pos]='0'
pos=pos-1
print(x)
elif valorMaq==110 and x[pos]=='1':
valorMaq=1
x[pos]='1'
pos=pos-1
print(x)
elif valorMaq==111 and x[pos]=='0':
valorMaq=111
x[pos]='0'
pos=pos-1
print(x)
elif valorMaq==111 and x[pos]=='1':
valorMaq=1000
x[pos]='1'
pos=pos-1
print(x)
################################################
elif valorMaq==1000 and x[pos]=='0':
valorMaq=1001
x[pos]='0'
pos=pos-1
print(x)
elif valorMaq==1000 and x[pos]=='1':
valorMaq=1000
x[pos]='1'
pos=pos-1
elif valorMaq==1001 and x[pos]=='0':
valorMaq=10
x[pos]='0'
pos=pos+1
print(x)
elif valorMaq==1001 and x[pos]=='1':
valorMaq=1
x[pos]='1'
pos=pos-1
print(x)
elif valorMaq==1010 and x[pos]=='1':
valorMaq=1010
x[pos]='1'
pos=pos+1
print(x)
elif valorMaq==1010 and x[pos]=='0':
valorMaq=0
x[pos]='0'
pos=pos+1
break
print(x)
x = ''.join(x)
print("Maximo comun divisor: ", x)
不管你写了什么，我确实查看了你的每一行代码。
\n\n您对第二条规则的实施是不正确的。Penrose 有 0 1 \xe2\x86\x921 1 L 但你编程了 0 1 \xe2\x86\x9211 0 L。所以将第 12 行到第 16 行更改为
\n\nelif valorMaq==0 and x[pos]==\'1\':\n valorMaq=1\n x[pos]=\'1\'\n pos=pos-1\n print(x)\n这是唯一错误的规则。然而，您遗漏了图灵机的一个重要想法：它可能是无限的，并且每当读取头移离当前定义的磁带时，它会自动将空白单元添加到磁带的任一端。您可以通过向每个pos更改的代码部分添加更多行来实现这一点。
但是，我建议您对代码进行彻底更改。您使代码变得比需要的更加困难。首先，您可以使用制表符进行缩进，但这在 Python 中并不是一个好主意——每一级缩进使用 4 个空格。
\n\n另一方面，你有很多重复的代码，这违反了 DRY（不要重复自己）原则。用数据结构（例如字典）替换你的算法来表示规则，并编写一个使用输入和该结构的小型引擎执行图灵机。例如，rules[(0, \'0\')]可以是(0, \'0\', +1)表示处于状态零的元组，向当前位置写入“0”字符，并向当前位置加 1（即向右移动一个单元格）。第二个生产将有rules[(0, \'1\')]状态(1, \'1\', -1)1，字符“1”，并向左移动。停止动作可以用机器永远无法移动的东西来表示，例如“无”。这样的代码会更容易理解和调试。
这是一些执行此操作的代码。我还改进了打印输出以显示磁带中的当前状态和位置，并删除了\'0\'输入两端都必须有一个额外字符的要求。我还使代码更加灵活、可扩展和可测试。我相信如何将彭罗斯展示的规则转换为我在规则字典中使用的格式是很清楚的，尽管为了方便和空间，我使用十进制数字而不是彭罗斯的二进制数字。这段代码中没有错误检查。我用一对数字（每个数字从 1 到 50）对此进行了测试，它总是以一元格式给出正确的最大公约数。彭罗斯的算法相当聪明——我从来没有想到过这个算法，它不使用额外的字符。
"""Calculate the greatest common divisor of two unary numbers using\nPenrose\'s algorithm for a Turing machine.\n\nSuggested by </sf/ask/3112718101/\nmachine-euclids-algorithm-for-finding-greatest-common-divisor-python>\nwhich itself uses Roger Penrose\'s *The Emperor\'s New Mind*, Oxford\nUniversity Press 1989 (paperback) p.41, the algorithm called EUC.\n\nNo error checking is done to the rules dictionary or the input line\nthat the correct format is followed.\n\nPossible changes:\n 1. Enforce Penrose\'s requirement that the ending position is to\n the right of the answer (perhaps with blanks between the answer\n and the position).\n a. Perhaps return \'\'.join(tape[:pos]).strip(BLANK) which\n removes anything at and right of the ending position.\n b. Perhaps check that only blanks are at and right of the\n ending position.\n"""\n\n# Constants for magic numbers\nBLANK = \'0\' # blank character\nSTOP = None # code to end the calcuation\nSTATEWIDTH = 3 # number of spaces to print current state in\n\n# A rules dictionary, each entry in the format\n# (oldstate, currentcharacter): (newstate, newcharacter, move_or_stop)\nEUC = {\n ( 0, \'0\'): ( 0, \'0\', +1), ( 0, \'1\'): ( 1, \'1\', -1), # state 0 = 0\n ( 1, \'0\'): ( 2, \'1\', +1), ( 1, \'1\'): ( 1, \'1\', -1), # state 1 = 1\n ( 2, \'0\'): (10, \'0\', +1), ( 2, \'1\'): ( 3, \'0\', +1), # state 2 = 10\n ( 3, \'0\'): ( 4, \'0\', +1), ( 3, \'1\'): ( 3, \'1\', +1), # state 3 = 11\n ( 4, \'0\'): ( 4, \'0\', +1), ( 4, \'1\'): ( 5, \'0\', +1), # state 4 = 100\n ( 5, \'0\'): ( 7, \'0\', -1), ( 5, \'1\'): ( 6, \'1\', -1), # state 5 = 101\n ( 6, \'0\'): ( 6, \'0\', -1), ( 6, \'1\'): ( 1, \'1\', -1), # state 6 = 110\n ( 7, \'0\'): ( 7, \'0\', -1), ( 7, \'1\'): ( 8, \'1\', -1), # state 7 = 111\n ( 8, \'0\'): ( 9, \'0\', -1), ( 8, \'1\'): ( 8, \'1\', -1), # state 8 = 1000\n ( 9, \'0\'): ( 2, \'0\', +1), ( 9, \'1\'): ( 1, \'1\', -1), # state 9 = 1001\n (10, \'0\'): ( 0, \'0\', STOP), (10, \'1\'): (10, \'1\', +1), # state 10 = 1010\n}\n\ndef print_situation(state, tape, pos, printlines):\n if printlines:\n print(str(state).rjust(STATEWIDTH), \'\'.join(tape))\n print(\'\'.rjust(STATEWIDTH), \'^\'.rjust(pos + 1))\n\ndef turing_machine(inputline, rules, printlines=True):\n tape = list(inputline)\n state = 0\n pos = 0\n print_situation(state, tape, pos, printlines)\n move = 1 # something other than STOP\n while move != STOP:\n # Do the next action\n state, tape[pos], move = rules[(state, tape[pos])]\n if move != STOP:\n pos += move\n else:\n pos += 1 # Penrose says all stops move right once\n # Add any needed blank characters to an end of the tape\n while pos < 0:\n tape.insert(0, BLANK)\n pos += 1 # pos is relative to left end of tape, so adjust both\n while pos >= len(tape):\n tape.append(BLANK) # left end not changed so pos not adjusted\n # Print current situation\n print_situation(state, tape, pos, printlines)\n return \'\'.join(tape).strip(BLANK)\n\nprint(turing_machine(\n input("Enter two unary numbers separated by a \'0\': "), EUC))\n当我输入2和6的代码时110111111，返回的结果是11which是2的一元代码，整个打印输出是：
0 110111111\n ^\n 1 0110111111\n ^\n 2 1110111111\n ^\n 3 1010111111\n ^\n 3 1010111111\n ^\n 4 1010111111\n ^\n 5 1010011111\n ^\n 6 1010011111\n ^\n 6 1010011111\n ^\n 6 1010011111\n ^\n 1 1010011111\n ^\n 2 1110011111\n ^\n 3 1100011111\n ^\n 4 1100011111\n ^\n 4 1100011111\n ^\n 5 1100001111\n ^\n 6 1100001111\n ^\n 6 1100001111\n ^\n 6 1100001111\n ^\n 6 1100001111\n ^\n 6 1100001111\n ^\n 1 1100001111\n ^\n 1 01100001111\n ^\n 2 11100001111\n ^\n 3 10100001111\n ^\n 3 10100001111\n ^\n 4 10100001111\n ^\n 4 10100001111\n ^\n 4 10100001111\n ^\n 4 10100001111\n ^\n 5 10100000111\n ^\n 6 10100000111\n ^\n 6 10100000111\n ^\n 6 10100000111\n ^\n 6 10100000111\n ^\n 6 10100000111\n ^\n 6 10100000111\n ^\n 1 10100000111\n ^\n 2 11100000111\n ^\n 3 11000000111\n ^\n 4 11000000111\n ^\n 4 11000000111\n ^\n 4 11000000111\n ^\n 4 11000000111\n ^\n 4 11000000111\n ^\n 5 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 6 11000000011\n ^\n 1 11000000011\n ^\n 1 011000000011\n ^\n 2 111000000011\n ^\n 3 101000000011\n ^\n 3 101000000011\n ^\n 4 101000000011\n ^\n 4 101000000011\n ^\n 4 101000000011\n ^\n 4 101000000011\n ^\n 4 101000000011\n ^\n 4 101000000011\n ^\n 4 101000000011\n ^\n 5 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 6 101000000001\n ^\n 1 101000000001\n ^\n 2 111000000001\n ^\n 3 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 4 110000000001\n ^\n 5 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 7 1100000000000\n ^\n 8 1100000000000\n ^\n 8 01100000000000\n ^\n 9 001100000000000\n ^\n 2 001100000000000\n ^\n 10 001100000000000\n ^\n 10 001100000000000\n ^\n 10 001100000000000\n ^\n 0 001100000000000\n ^\n11\n| 归档时间： |
|
| 查看次数： |
2322 次 |
| 最近记录： |