- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在执行一个计算方程式的程序:F(n) = F(n-1) + 'a' + func1(func2(F(n-1)))。
func1 将每个“a”变成“c”,每个“c”变成“a”。
func2 反转字符串(例如“xyz”变为“zyx”)。
我想计算 F(10**2017) 的第 K 个字符。基本规则为 F(0) = ""(空字符串),示例为 F(1) = "a"、F(2) = "aac"等。
我如何有效地做到这一点?
我的代码的基本部分是这样的:
def op1 (str1):
if str1 == 'a':
return 'c'
else:
return 'a'
def op2 (str2):
return str2[::-1]
sinitial = ''
while (counter < 10**2017):
Finitial = Finitial + 'a' + op1(op2(Finitial))
counter += 1
print Finitial
最佳答案
让我们首先修复您的原始代码并定义一个函数来计算 F(n)
对于小n
.我们还将打印出 F
的前几个值。 .以下所有代码均适用于 Python 3;如果您使用的是 Python 2,则需要进行一些小的更改,例如替换 str.maketrans
与 string.maketrans
和 range
与 xrange
.
swap_ac = str.maketrans({ord('a'): 'c', ord('c'): 'a'})
def F(n):
s = ''
for _ in range(n):
s = s + 'a' + s[::-1].translate(swap_ac)
return s
for n in range(7):
print("F({}) = {!r}".format(n, F(n)))
这给出了以下输出:
F(0) = ''
F(1) = 'a'
F(2) = 'aac'
F(3) = 'aacaacc'
F(4) = 'aacaaccaaaccacc'
F(5) = 'aacaaccaaaccaccaaacaacccaaccacc'
F(6) = 'aacaaccaaaccaccaaacaacccaaccaccaaacaaccaaaccacccaacaacccaaccacc'
此时的一些观察:
F(n)
是一个长度为 2**n-1
的字符串.这意味着 F(n)
成长快。计算 F(50)
已经需要一些重要的硬件:即使我们每位存储一个字符,我们也需要超过 100 TB 的空间来存储完整的字符串。 F(200)
具有比太阳系中估计的原子更多的特征。所以计算的想法F(10**2017)
直接是可笑的:我们需要一种不同的方法。
通过构造,每个 F(n)
是 F(n+1)
的前缀.所以我们真正拥有的是一个定义良好的 infinite 字符串,其中每个 F(n)
仅仅给了我们第一个2**n-1
该无限字符串的字符,我们正在计算它的 k
第字符。出于任何实际目的,F(10**2017)
还不如那个无限字符串:例如,当我们进行计算时,我们不需要检查 k < 2**(10**2017)-1
, 因为 k
超过这个甚至不能用这个宇宙中的正常二进制表示法表示。
幸运的是,字符串的结构很简单,可以计算k
。第一个字符直接是直截了当的。当我们查看偶数和奇数位置的字符时,就会出现主要线索:
>>> F(6)[::2]
'acacacacacacacacacacacacacacacac'
>>> F(6)[1::2]
'aacaaccaaaccaccaaacaacccaaccacc'
偶数 位置的字符只是在 a
之间交替和 c
(并且根据构造可以直接证明这是真的)。所以如果我们的 k
是偶数,我们可以简单看一下是否k/2
是奇数还是偶数来确定我们是否会得到 a
或 c
.
奇怪的位置呢?嗯F(6)[1::2]
应该看起来有点眼熟:它只是 F(5)
:
>>> F(6)[1::2] == F(5)
True
同样,可以直接证明(例如,通过归纳法)这不仅仅是巧合,而且 F(n+1)[1::2] == F(n)
对于所有非负 n
.
我们现在有一种有效的方法来计算 k
无限字符串中的第 th 个字符:if k
是偶数,我们只看k/2
的奇偶性.如果k
是奇数,那么我们就知道位置k
的字符等于位置(k-1)/2
.所以这是计算该字符的第一个解决方案:
def char_at_pos(k):
"""
Return the character at position k of the string F(n), for any
n satisfying 2**n-1 > k.
"""
while k % 2 == 1:
k //= 2
return 'ac'[k//2%2]
并检查这是否正确:
>>> ''.join(char_at_pos(i) for i in range(2**6-1))
'aacaaccaaaccaccaaacaacccaaccaccaaacaaccaaaccacccaacaacccaaccacc'
>>> ''.join(char_at_pos(i) for i in range(2**6-1)) == F(6)
True
但我们可以做得更好。我们有效地盯着 k
的二进制表示, 删除所有尾随 '1'
s 和下一个 '0'
,然后简单地查看下一位以确定我们是否有 'a'
或 'c'
.识别尾随的 1 可以通过位操作技巧来完成。这为我们提供了以下半混淆的无循环解决方案,我将其留给您展开:
def char_at_pos2(k):
"""
Return the character at position k of the string F(n), for any
n satisfying 2**n-1 > k.
"""
return 'ac'[k//(1+(k+1^k))%2]
再次,让我们检查一下:
>>> F(20) == ''.join(char_at_pos2(i) for i in range(2**20-1))
True
最后的评论:这是一个非常著名且研究充分的序列:它被称为龙曲线序列,或 regular paper-folding sequence , 并且是 sequence A014577在整数序列的在线百科全书中。某些 Google 搜索可能会为您提供许多其他方法来计算其元素。另见 this codegolf question .
关于python - 用指数有效地计算数学公式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44864264/
我得到了以下 Excel 公式来计算法国系统贷款利息: =+G15*B15/(1-(1+G15)^(-H15)) 地点: G15 = 1.33% B15 = importe H15 = plazo 由
我必须构建一个像这样的序列 (amount-(amount/36*1)) + (amount-(amount/36*1 + amount-amount/36*2)) + (amount-(amount
在R语言的绘图函数中,如果文本参数是合法的R语言表达式,那么这个表达式就被用Tex类似的规则进行文本格式化。 y <- function(x) (exp(-(x^2)/2))/sqrt(2
我喜欢转换旧的 BASIC 游戏——我遇到了一个有这个奇怪公式的游戏。目前我正在用 Pascal 编写,但我可以用任何语言编写。翻遍代码后,我找不到这个 var 是否在使用,但仍然想知道当时 BASI
我需要在 C 中实现这个数学公式: 我写了一段代码: #include int c(int n, int k) { if(k == 0) return n; if(c
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 10 年前。 Improve thi
是否有任何常规范式来表示可以被计算机读取的数学公式? 我正在研究一些数学问题,并有某种 TDD 方法来解决它。每次我陷入一个证明(或者只是我还没有证明,但是对结果应该是什么的一些直觉)时,我倾向于编写
我正在尝试用 C 语言实现一个数学公式来计算特定 Runescape 级别所需的 XP,但我没有得到正确的输出。 1 级给出“75”XP,99 级给出“11059837”。我的实现有什么问题吗?我想不
我想在绘图中添加一个包含 Latex 公式的 geom_text(),以描述 2 个矩阵中每个值的平均百分比: library(latex2exp) library(ggplot2) library(
我是一名优秀的程序员,十分优秀!