作业帮 > 数学 > 作业

用matlab找出1、2、3、……、20个自然数其中所有组合,使得它们的和为48.统计出所有的组合

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/11/01 06:55:35
用matlab找出1、2、3、……、20个自然数其中所有组合,使得它们的和为48.统计出所有的组合
首先对该问题做如下分析:
1、在20个数中任意取0个到20个数相加,共有2^20种可能.每一个数可以可以选择‘取’或者‘不取’两个状态.故考虑最外面的循环为考虑着2^20种所有可能.
-----------------------------------------------------------------
2、这2^20种可能与二进制的关系:为简便说明,以2^5为例:
【5 4 3 2 1】
【0 1 0 1 0】
上面的两个数组,前者是可以选取的数,后者是一个二进制数组,1代表选取状态,0则为不选取状态;如上例,实际上选择了2,4.这样的二进制数组可以从【0 0 0 0 0】到【1 1 1 1 1】;共有2^5种可能.
-----------------------------------------------------------------
3、以下结合程序,逐步分析每句的作用.%表示注释
close all;clear all;clc; %一些必要的变量清除等,是良好的习惯
solutionNumber=0; %求解结果数目计数初始化
x=1:20; %可选取数的数组
for i=1:2^20 %第一个大循环,考虑所有可能
sum=0; %每一种大循环可能的计算和的初始化
for k=1:20 %对二进制的每一位进行遍历
if bitget(i,k)==1 %选择i的二进制数的第k位(从最低位开始)进行判断
sum=sum+x(k);
if sum>48 %此处对于减少计算量十分重要,如果到某一步和已经超过48了,再计算下去没有意义了,后面用个break直接跳出循环.
break;
end
end
end
if sum==48 %对于符合要求的结果
solutionNumber=solutionNumber+1; %解的数目的计数器增加1
s=1;选取的数的计数
clear m;%存储选取的数的数组的初始化
for j=1:20 %循环变量初始化
if bitget(i,j)==1 对于二进制为1的位,将相应的数存入m
m(s)=j;
s=s+1;
end
end
disp(m);
end
end
disp(['求解完成!共有' num2str(solutionNumber) '种可能.']);
----------------------------------------------------------------
4、附注,bitget(i,k)的作用将i转换为二进制数,然后取其第k位(从最低位开始计数).这样,如果bitget(i,4)=1可以这样理解.
位数 【20 19 18 省略 6 5 4 3 2 1】
二进制 【 x x x 省略 x x 1 x x x】x代表0或1
如此,第四位为1可以理解为4被选取了.以上为对if bitget(i,k)==1这一判断过程的说明.
----------------------------------------------------------------
以下为纯代码,方便复制
close all;clear all;clc;
solutionNumber=0;
x=1:20;
for i=1:2^20
sum=0;
for k=1:20
if bitget(i,k)==1
sum=sum+x(k);
if sum>48
break;
end
end
end
if sum==48
solutionNumber=solutionNumber+1;
s=1;
clear m;
for j=1:20
if bitget(i,j)==1
m(s)=j;
s=s+1;
end
end
disp(m);
end
end
disp(['求解完成!共有' num2str(solutionNumber) '种可能.']);
----------------------------------------------------------------
以下为测试结果,由于行数很多,只截取最后几行.
10 18 20
2 3 4 19 20
1 3 5 19 20
4 5 19 20
1 2 6 19 20
3 6 19 20
2 7 19 20
1 8 19 20
9 19 20
共有1674种可能.
-----------------------------------------------------------------
计算时间大约在40s-60s,视计算机速度.