最短加法链
加法链是从1开始的整数序列，其中除初始1以外的每一个整数都是前两个整数的和。
例如，这里有一个加法链：
[1, 2, 3, 4, 7, 8, 16, 32, 39, 71]以下是使它成为一个加法链的金额：
1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
3 + 4 = 7
1 + 7 = 8
8 + 8 = 16
16 + 16 = 32
7 + 32 = 39
32 + 39 = 71在这个挑战中，您将获得一个正整数n，并且必须输出以n结尾的最短加法链之一。
示例--请注意，有许多可能的输出，您需要找到的只是一个同样短的加法链：
1: [1]
2: [1, 2]
3: [1, 2, 3]
4: [1, 2, 4]
5: [1, 2, 3, 5]
6: [1, 2, 3, 6]
7: [1, 2, 3, 4, 7]
11: [1, 2, 3, 4, 7, 11]
15: [1, 2, 3, 5, 10, 15]
19: [1, 2, 3, 4, 8, 11, 19]
29: [1, 2, 3, 4, 7, 11, 18, 29]
47: [1, 2, 3, 4, 7, 10, 20, 27, 47]
71: [1, 2, 3, 4, 7, 8, 16, 32, 39, 71]禁止标准I/O规则等标准漏洞。代码高尔夫:最少字节获胜。
回答 5
Code Golf用户
发布于 2017-05-28 19:53:42
Pyth，13字节
h-DsM^N2/#QyS给出按字母顺序排列的第一条最短链。它相当慢，但不是那么糟糕- 19使用pypy在大约30秒内完成。
丹尼斯的解决方案中的一些想法。
我真的很喜欢这个-有很多巧妙的技巧。
解释：
h-DsM^N2/#QyS
h-DsM^N2/#QySQ Implicit variable introduction
SQ Inclusive range, 1 to input.
y Subsets - all subsets of the input, sorted by length then lexicographically
Only sorted subsets will be generated.
Our addition chain will be one of these.
/#Q Filter for presence of the input.
D Order by
- What's left after we remove
^N2 All pairs of numbers in the input
sM Summed
h Output the list that got sorted to the front.这仍然是有点难以理解，但让我尝试解释更多的细节。
我们从ySQ开始，它给出了[1, 2, ... Q]的所有可能的有序子集，并按大小的顺序增加。最短的加法链无疑是其中之一，但我们需要找到它。
我们要做的第一件事是过滤列表，使其只保留包含Q的列表。我们用/#Q来做这件事。
接下来，在删除某个函数的结果之后，我们根据剩下的内容对列表进行排序。-D在移除某些内容后，按剩余命令进行排序。
我们删除的是sM^N2，其中N是我们要从其中删除的列表。^N2给出了N的笛卡儿乘积，并给出了N中所有可能的两个元素对。然后，sM对每对进行求和。
做完这个手术后，最小的可能结果是什么？那么，输入列表中最小的元素肯定会保持不变，因为所有的数字都是正数，所以任何两个数字的和都会大于最小的数。至少有一个数字，因为我们检查了输入是否存在于列表中。因此，当除最小数之外的每一个数都是列表中其他两个数之和，而列表中最小数为1时，可能的最小结果是。在这种情况下，排序键将是[1]。这些要求意味着列表必须是一个加法链。
所以，我们对前面的加法链进行排序。请记住，y按大小的顺序给出了它的子集，所以排序到前面的列表必须是最短的加法链之一。h选择该列表。
Code Golf用户
发布于 2017-05-28 17:00:18
布氏对数，14字节
∧≜;1{j⊇Ċ+}ᵃ⁽?∋使用迭代深化构建所有可能的加法链的强力提交，当找到包含其正确参数的链时停止。这是一个函数提交，它通过它的右参数(通常称为输出)输入，并通过它的左参数(通常称为输入)输出；这样做有些争议，但是关于这个主题的投票最高的元答案说它是合法的(并且这样做符合我们对函数的正常I/O默认值)。如果我们以更常规的方式使用输入和输出，这将是16字节(∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧)，因为程序的右侧将无法使用隐式约束(因此需要禁用该约束，并以2字节为代价提供一个新的显式约束)。
解释
∧≜;1{j⊇Ċ+}ᵃ⁽?∋
∧ Disable implicit constraint to read the left argument
≜; ⁽ Evaluation order hint: minimize number of iterations
{ }ᵃ Repeatedly run the following:
1 ᵃ From {1 on the first iteration, results seen so far otherwise}
j Make {two} copies of each list element
⊇ Find a subset of the elements
Ċ which has size 2
+ and which sums to {the new result for the next iteration}
∋ If the list of results seen so far contains {the right argument}
? Output it via the left argument {then terminate}这里一个有趣的微妙之处是在第一次迭代中所发生的事情，其中输入是一个数字，而不是其他迭代中的一个列表；我们从数字1开始，复制每个数字(生成数字11)，然后找到它的2位数字子序列(也就是数字11)。然后我们取它的数字和，也就是2，这样序列就会开始[1,2]，就像我们想要的那样。在未来的迭代中，我们将从[1,2]这样的列表开始，将其加倍到[1,2,1,2]，然后采用两个元素子序列([1,1]、[1,2]、[2,1]或[2,2])；显然，每个元素的和都将是加法链的下一个元素。
这里需要计算顺序提示，特别是≜组件，这有点让人沮丧(默认情况下，ᵃ从内部而不是外部获取其计算顺序提示，因此使用≜来解决这个问题非常粗糙)。
Code Golf用户
发布于 2017-05-27 16:05:55
果冻，17字节
’ŒP;€µ+þ;1Fḟ@µÐḟḢ以指数时间输出字典第一解。
是如何工作的
’ŒP;€µ+þ;1Fḟ@µÐḟḢ Main link. Argument: n (integer)
’ Decrement; n-1.
ŒP Powerset; generate all subarrays of [1, ..., n-1], sorted first
by length, then lexicographically.
;€ Append n to all generate subarrays.
µ µÐḟ Filterfalse; keep only subarrays for which the chain between the
two chain separators (µ) returns a falsy value.
µ Monadic chain. Argument: A (array of integers)
+þ Add table; compute the sums of all pairs of elements in x,
grouping the results by the right addend.
;1 Append 1 to the resulting 2D array.
F Flatten the result.
ḟ@ Filterfalse swapped; remove all elements of A that appear in
the result. This yields an empty list for addition chains.
Ḣ Head; select the first result.https://codegolf.stackexchange.com/questions/123066
复制相似问题
腾讯云开发者
