挑数字
从自然数中挑选K个数（可以重复选取）组成一个数组，使得其中不超过3个元素之和可以连续取到1~N，现已知N。求数组中元素个数最少且最大值最小的一个。比如N=10，（1,2， 4 ，4），（1,2,2,6）和（1,2,3,7）都满足个数最少，但（1,2，4,4中最大值为4）。所以结果是（1,2,4,4）。
1=1
2=2
1+2=3
4=4
1+4=5
2+4=6
1+2+4=7
4+4=8
1+4+4=9
2+4+4=10
现在N=10000，求该数组。 本帖最后由 northwolves 于 2023-12-4 15:23 编辑
看看我的数据正确与否：
1 {1}
2 {1,1}
3 {1,2}
4 {1,1,2}
5 {1,2,2}
6 {1,2,3}
7 {1,2,4}
8 {1,2,3,3}
9 {1,2,3,4}
10 {1,2,4,4}
11 {1,2,4,5}
12 {1,2,4,6}
13 {1,2,4,7}
14 {1,2,4,8}
15 {1,2,3,6,6}
16 {1,2,3,6,7}
17 {1,2,3,6,8}
18 {1,2,3,6,9}
19 {1,2,3,6,10}
20 {1,2,3,6,11}
21 {1,2,3,6,12}
22 {1,2,4,7,13}
23 {1,2,4,7,14}
24 {1,2,3,6,10,11}
25 {1,2,3,6,10,12}
26 {1,2,3,7,11,12}
27 {1,2,3,7,11,13}
28 {1,2,3,7,11,14}
29 {1,2,4,8,13,14}
30 {1,2,3,6,10,17}
31 {1,2,3,6,10,18}
32 {1,2,3,6,10,19}
33 {1,2,3,6,10,20}
northwolves 发表于 2023-12-4 12:42
看看我的数据正确与否：
1 {1}
2 {1,1}
怎么算出来的？ aimisiyou 发表于 2023-12-4 13:23
怎么算出来的？
f:=Module[{x=Prepend/@Union,Floor]]]},y=Select)]]=={}&];First@SortBy];Table[{n,f},{n,20}] 未返回结果的项数加1即可
{{1,{1}},{2,{1,1}},{3,{1,2}},{4,{1,1,2}},{5,{1,2,2}},{6,{1,2,3}},{7,{1,2,4}},{8,{1,2,3,3}},{9,{1,2,3,4}},{10,{1,2,4,4}},{11,{1,2,4,5}},{12,{1,2,4,6}},{13,{1,2,4,7}},{14,{1,2,4,8}},{15,First[{}]},{16,{1,2,3,6,7}},{17,{1,2,3,6,8}},{18,{1,2,3,6,9}},{19,{1,2,3,6,10}},{20,{1,2,3,6,11}}} 不知道是否最优解，但在n>15时， {1,2,3,6}，{1,2,3,7}， {1,2,4,7}, { {1,2,4,8}必出。 本帖最后由 aimisiyou 于 2023-12-5 12:40 编辑
一个大佬给出他的思路建议:
“一个思路，不一定正确，供参考。
分三步取数，假如N=100
第一步，取从1开始的连续自然数1-4，两两相加可以得到连续整数1-7；
第二步，增加自然数，从8开始，递增4+1，把两数相加所得的连续数段适当延长，增加8，可以使连续的数段延长至1-12，增加13、18，可以使连续的数段延长至1-22；
用1-4、8、13、18，求三个数的和，连续数中最大可得到35（4+13+18）；
第三步，从36开始，依次递增22+1，得到36、59、82，三数和可得连续数1-104，满足N=100，可将36-82分别减去4，得到：
1-4、8-18、32-78共10个数，最大值78。
如果第一步取1-3，两两相加可得到连续自然数1-5；
第二步，从6开始，依次递增3+1，取6、10、14，使得两数和所得连续数段延长至1-17；
1-3、6-14共6个数，求三数之和，连续数中最大可得到27（3+10+14）；
第三步，从28开始，按17+1递增，取数28、46、64、82、100，三数和可得连续数1-117，满足N=100，可将46-100四个数各减17，得到：
1-3、6-14、28、29-83，共11个数，最大值83。
如果第一步取1-5，第二步从10开始，依次取10、16、22三数，两数和可得连续数1-27；
第三步从44开始，递增27+1，取44、72、100，综合N=100，可取44、45、73：
1-5、10-22、44、45、73，共11个数，最小值73。”
他给出的一个答案：1-18（共18个）、36-340（递增19，共17个）、667-9642（递增359，共26个），总共61个，最大9642。 我目前能做到60，感覺是最少了
S=[]
A=[0,0,
1,2,3,4,5,6,7,8,9,10,
11,12,13,14,15,16,17,18,19,20,
21,42,64,86,108,130,152,174,196,218,
240,262,284,306,328,350,372,394,416,438,
460,920,1402,1884,2366,2848,3330,3812,4294,4776,
5258,5740,6222,6704,7186,7668,8150,8632,9114,9519];
for(i in A)for(j in A)for(k in A)if(i<j&j<k)S+A+A]=1;
for(i=1;i<=10000;++i)if(!S)console.log(i); aimisiyou 发表于 2023-12-5 12:14
一个大佬给出他的思路建议:
“一个思路，不一定正确，供参考。
随机测试，n=100, {1, 2, 3, 6, 10, 17, 28, 40, 46, 52} 共10个数，最大值52满足条件。 找到几组更小一些的：
\begin{array}{cccccccccc}
1 & 2 & 4 & 7 & 14 & 21 & 29 & 38 & 46 & 47 \\
1 & 2 & 4 & 7 & 14 & 21 & 30 & 38 & 46 & 48 \\
1 & 2 & 4 & 7 & 14 & 21 & 30 & 39 & 47 & 48 \\
1 & 2 & 4 & 7 & 14 & 21 & 30 & 40 & 46 & 48 \\
1 & 2 & 4 & 7 & 14 & 21 & 31 & 40 & 48 & 49 \\
1 & 2 & 3 & 6 & 12 & 19 & 29 & 36 & 43 & 51 \\
1 & 2 & 3 & 6 & 10 & 17 & 28 & 40 & 46 & 52 \\
\end{array}
页:
[1]
2