找回密码
 欢迎注册
查看: 608|回复: 11

[求助] 挑数字

[复制链接]
发表于 2023-12-4 08:30:23 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
从自然数中挑选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,求该数组。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-4 12:42:18 | 显示全部楼层
本帖最后由 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}

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-12-4 13:23:10 | 显示全部楼层
northwolves 发表于 2023-12-4 12:42
看看我的数据正确与否:
1        {1}
2        {1,1}

怎么算出来的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-4 15:31:34 | 显示全部楼层
  1. f[n_]:=Module[{x=Prepend[1]/@Union[Sort/@Tuples[Range[n/2+5],Floor[Log2[n]]]]},y=Select[x,Complement[Range@n,Union[Total/@(Subsets[#,3])]]=={}&];First@SortBy[y,Last]];Table[{n,f[n]},{n,20}]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-4 15:32:27 | 显示全部楼层
未返回结果的项数加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}}}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-4 15:34:43 | 显示全部楼层
不知道是否最优解,但在n>15时, {1,2,3,6},{1,2,3,7}, {1,2,4,7}, { {1,2,4,8}必出。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-12-5 12:14:08 | 显示全部楼层
本帖最后由 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。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-5 13:12:22 | 显示全部楼层
我目前能做到60,感覺是最少了
  1. S=[]
  2. A=[0,0,
  3. 1,2,3,4,5,6,7,8,9,10,
  4. 11,12,13,14,15,16,17,18,19,20,
  5. 21,42,64,86,108,130,152,174,196,218,
  6. 240,262,284,306,328,350,372,394,416,438,
  7. 460,920,1402,1884,2366,2848,3330,3812,4294,4776,
  8. 5258,5740,6222,6704,7186,7668,8150,8632,9114,9519];
  9. for(i in A)for(j in A)for(k in A)if(i<j&j<k)S[A[i]+A[j]+A[k]]=1;
  10. for(i=1;i<=10000;++i)if(!S[i])console.log(i);
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-5 16:35:26 | 显示全部楼层
aimisiyou 发表于 2023-12-5 12:14
一个大佬给出他的思路建议:
“一个思路,不一定正确,供参考。

随机测试,n=100, {1, 2, 3, 6, 10, 17, 28, 40, 46, 52} 共10个数,最大值52满足条件。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-12-5 21:48:51 | 显示全部楼层
找到几组更小一些的:
\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}

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-2-23 05:24 , Processed in 0.057519 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表