本次挑战基于。
编写最短的程序或函数，当给定一些自然数时nnn，输出年代（名词）年代（n）S(n)，这是生成至少包含 nnn原始字符串的副本，仅使用全选、复制和粘贴操作。
在数学答案中，年代（名词）年代（n）S(n)满足公式
S(n) = \min_{i=1, \ldots, 8} 5 \lceil \log_4(n/u_i) \rceil+c_i
在哪里（C我，你我）（C我，你我）(c_i, u_i)是来自元组集合的元组我= { （0，1 ），（3，2 ），（7，6 ），（4，3 ），（8，9 ），（12，27 ），（16，81 ），（6，5 ）}我={（0，1），（3，2），（7，6），（4，3），（8，9），（12，二十七），（16，81），（6，5）} I = \{ (0,1), (3,2), (7,6), (4,3), (8,9), (12,27), (16,81), (6,5) \}。
测试用例
1 => 0
2 => 3
4 => 5
8 => 8
16 => 10
32 => 13
64 => 15
128 => 18
256 => 20
512 => 23
1024 => 25
2048 => 28
4096 => 30
8192 => 33
16384 => 35
32768 => 38
65536 => 40
131072 => 43
262144 => 45
524288 => 48
1048576 => 50
2097152 => 53
100000 => 42
\endgroup
14
10 个回答
10
3，48 字节
f=lambda n:n>1and-~min(i+f(n/i)for i in b"")
50 字节
f=lambda n:n>1and min(i+1+f(n/i)for i in[2,3,4,5])
不必考虑公式。相反，它实现了，其中每个步骤都会为该数量的操作加上一个创建 2、3、4 或 5 个字符串副本。
输出与 4 的幂的公式得出的测试用例不匹配，但正如 Bubbler 指出的那样，这是由于数学 SE 帖子中的公式拼写错误造成的。
\endgroup
3
-
\begingroup
您可以使用 在第二个中保存一个字节i-~f。
\endgroup
– -
\begingroup
@Shaggy 我将其包含在内只是为了作为 48 字节的更易读的版本。
\endgroup
– -
\begingroup
啊，好的。48b" "字节中的内容是做什么的？我不明白。
\endgroup
–
|
Google 表格，68 字节
=SORTN(5*CEILING(LOG(A1/{1;2;6;3;9;27;81;5},4))+{1;3;7;4;8;12;16;6})
\endgroup
|
JavaScript（ES6），98 字节
基本上是挑战中给出的（固定）公式的直接实现。
with(Math)f=n=>min(...[81,27,9,6,5,3,2,1].map((v,i)=>ceil(log(n/v)/log(4))*5-~(37115838>>i*4&15)))
\endgroup
|
，15
xnor 的 50 字节 Python 解决方案的端口。
f ©5ò2ÈÒßU/XÃrm
\endgroup
|
，41字节
f(1)=0.
f(N)=[f(N/>I)+I+1:I in 2..5].min.
相同的方法：递归遍历情况以ctrl+A C V{1,4}获得至少 N 个字符作为结果。
在标题部分的帮助下table，它几乎立即计算了所有测试用例。由于/>执行 ceil-ed 整数除法的运算符，所有中间参数都是整数，没有任何复杂性，我们可以简单地将 1 作为基本情况进行模式匹配。
Picat 中存在按位非运算符~，但它不喜欢将两个符号-~并排放置，因此通常的-~技巧不会节省任何字节。
\endgroup
|
，23
"D1›Di4L+DŠ/®δ.V+>ß"©.V
的移植，因此请务必也为该答案点赞。
仍然很长，因为 05AB1E 对于递归函数来说非常冗长。
或（在输出所有测试用例之前它会超时）。
使用给定的公式将改为32 个：
•¬òÃ,v₅aw°Üÿ∊•82в2ôε`Š/4.nî5*+}ß
或。
解释：
使用递归方法：
f(n) = \begin{cases}
0, & \text{if $n\leq1$} \\
\min(f(\frac{n}{2})+3, f(\frac{n}{3})+4, f(\frac{n}{4})+5, f(\frac{n}{5})+6), & \text{if $n>1$}
\end{cases}
"..." # Define the recursive string explained below
© # Store it in variable `®` (without popping)
.V # Pop and evaluate it as 05AB1E code
# (after which the result is output implicitly)
D # Duplicate the current value n
# (which will use the implicit input in the first iteration)
1› # Pop and check whether it's larger than 1
D # Duplicate this check
i # Pop the copy, and if it's truthy:
4L # Push list [1,2,3,4]
+ # Add the truthy check that's still on the stack: [2,3,4,5]
D # Duplicate this list
Š # Tripleswap to [2,3,4,5],n,[2,3,4,5]
/ # Divide [n/2,n/3,n/4,n/5]
δ # Map over each value:
® .V # And do a recursive eval to `®`
+ # Then add the values in the two lists together:
# [2+f(n/2),3+f(n/3),4+f(n/4),5+f(n/5)]
> # Increase each by 1
# [3+f(n/2),4+f(n/3),5+f(n/4),6+f(n/5)]
ß # Pop and leave the minimum
# (implicit else: use the duplicated falsey check, aka 0)
•¬òÃ,v₅aw°Üÿ∊• # Push compressed integer 50972899172091152076282460330
82в # Convert it to base-82 as list:
# [1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16]
2ô # Split it into pairs:
# [[1,0],[2,3],[3,4],[5,6],[6,7],[9,8],[27,12],[81,16]]
ε # Map over each pair [u,c]:
` # Pop and push both values to the stack
Š # Triple-swap u,c to c,i,u, where i is the implicit input
/ # Divide the input by u
4.n # Take log_4 of it
î # Ceil it
5* # Multiply by 5
+ # Add c
}ß # After the map: pop and leave the minimum
# (which is output implicitly as result)
以了解为什么•¬òÃ,v₅aw°Üÿ∊•是50972899172091152076282460330 和•¬òÃ,v₅aw°Üÿ∊•82в是[1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16]。
\endgroup
|
，49 45字节
f:$->n->(n>1)?[2..5|map=>[+1+f//n<=&]|min]->0
xnor 的 50 字节的端口。
，71字节
$->n->min map[0 1 3 2 7 6 4 3 8 9 12 27 16 81 6 5]=>[&+5*ceil log//n&4]
OP中的公式。
\endgroup
|
，24字节
ＦＮ⊞υ∨¬ι⁺³⌊Ｅ⁴⁺κ§υ÷ι⁺²κＩ⊟υ
链接为代码的详细版本。说明：基于 @xnor 的方法，但使用动态规划而不是递归。
ＦＮ
1计算到 的所有结果n。请注意，循环变量1小于正在计算的结果的索引，但这实际上节省了字节，因为⌈i/k-1⌉=(i-1)//k这只是整数除法。
⊞υ∨¬ι⁺³⌊Ｅ⁴⁺κ§υ÷ι⁺²κ
的结果1刚刚好1，而其他迭代的结果是之前四次计算结果中最好的。
Ｉ⊟υ
输出的结果n。
\endgroup
|
，51 字节
f=(n,i=6)=>n>1&&Math.min(i+f(n/--i),i>2?f(n,i):1/0)
\endgroup
|
，26 个半字节（13 个字节）
`; 1 -@$ 0 `/ . +~,4 + _ * @$ +$~ [
另一种递归方法“在每个步骤尝试 1、2、3 或 4 次粘贴”。
Nibbles 仅具有整数算术，因此我们不能（轻松地）在每个递归步骤中倒数并除以目标（如在中使用）。
但是，Nibbles 确实将程序输入作为所有递归调用中的全局变量记住，因此我们可以简单地计算迄今为止的字符串副本（从 1 开始）并在到达程序输入时停止，无论如何，这对我来说更直观。
`; 1 -@$ 0 `/ . +~,4 + _ * @$ +$~ [ # full program; input is stored in variable @
`; 1 # launch recursive function starting with copies=1
# (stored in variable $)
-@$ # stop when input <= copies-so-far
0 # and return zero
# otherwise return
`/ [ # minimum of
. # map over
+~,4 # i in 2..5
+ # sum of
_ # recursive call using
* @$ # copies-so-far * i
+$~ # and i+1 (steps needed to multiply copies by i)
\endgroup
|
我认为当您全选、复制然后粘贴时，粘贴不会覆盖选择内容而是附加到它？
\endgroup
–
“包含原始字符串的 n 个副本”是指至少 n 个，还是正好 n 个？
\endgroup
–
我不明白为什么F（4 ）= 6F（4）=6f(4)=6。难道你不能通过全选、复制、粘贴、粘贴、粘贴这 5 个操作将数量翻四倍吗？由于粘贴操作如你所说是附加的，因此这里只需要 3 个。
\endgroup
–
我浏览了 math.se 帖子，我认为公式中有一个拼写错误：(1,1) 应该是 (0,1)。此更改会影响所有采用 4^k 形式的测试输入。也在 math.se 帖子上添加了一条关于此问题的评论。
\endgroup
–
固定公式与最多 1e6 的算法解决方案
\endgroup
–
|