[已答复] n个数相加小于等于整数n0的所有情况?

[复制链接]
szzejz 发表于 2020-11-20 23:08:50
n个数相加小于等于整数n0的所有情况?目前我能做的就是for循环,不过效率及其低下,有没有好的方法,下附一个n=10的代码。

function index=JJ(n0)


index1=[];
k=1;
for i1=0:n0
    for i2=0:n0
        for i3=0:n0
            for i4=0:n0
                for i5=0:n0
                   for i6=0:n0
                      for i7=0:n0
                         for i8=0:n0
                             for i9=0:n0
                                 for i10=0:n0
                                  if (i1+i2+i3+i4+i5+i6+i7+i8+i9+i10)<=n0                              
                                      index1(:,k)=[i1 i2 i3 i4 i5 i6 i7 i8 i9 i10]';
                                       k=k+1;
                                  end

                                 end
                             end
                         end
                      end
                   end
                end
            end
        end
    end
end

index=index1;      




end



10 条回复


TouAkira 发表于 2020-11-20 23:47:21

szzejz 发表于 2020-11-21 15:49:24
TouAkira 发表于 2020-11-20 23:47
跟这个类似
https://www.ilovematlab.cn/thread-603548-1-1.html

你好,我是想打印所有的排列情况,不仅仅是有多少个情况。不过谢谢你的回答。

coolchen302 发表于 2020-11-21 18:44:05
循环要优化,速度能提升非常多吧
for i2=0:n0-i1
for i3=0:n0-i1-i2
...

TouAkira 发表于 2020-11-21 19:10:19
szzejz 发表于 2020-11-21 03:49
你好,我是想打印所有的排列情况,不仅仅是有多少个情况。不过谢谢你的回答。 ...
Lykin000 发表于 2020-11-9 21:31
要展示每种方法是如何分的
maple1314168 发表于 2020-11-9 21:43
10/20那道题,先拆分,不考虑顺序。得到42组。
在42组中,各自排序得到所有的可能
自己弄弄吧。

maple1314168 介绍过思路,当然要是现成的代码,那是没有的。

悟得 发表于 2020-11-21 20:44:15
很典型的一道用递归解决的排列组合问题。

szzejz 发表于 2020-11-21 21:46:52
悟得 发表于 2020-11-21 20:44
很典型的一道用递归解决的排列组合问题。

你好,我也查过可以利用递归,但我不知道应该怎么设计这个递归呢?

szzejz 发表于 2020-11-21 21:50:36
coolchen302 发表于 2020-11-21 18:44
循环要优化,速度能提升非常多吧
for i2=0:n0-i1
for i3=0:n0-i1-i2

谢谢你的回答,这样应该可以优化循环,但这个只是个例子。其实我需要计算100个数相加的小于一个整数n0,甚至更多,这样的话100的循环也是不现实的,我也想到可以利用递归,但是我不知道应该怎样设计这个递归?

szzejz 发表于 2020-11-22 10:22:15
TouAkira 发表于 2020-11-21 19:10
maple1314168 介绍过思路,当然要是现成的代码,那是没有的。

那如果是一个高维的向量(超过10维)的排列,应该怎么做呢?

maple1314168 发表于 2020-11-22 23:51:45
本帖最后由 maple1314168 于 2020-11-22 23:53 编辑
szzejz 发表于 2020-11-22 10:22
那如果是一个高维的向量(超过10维)的排列,应该怎么做呢?

你的电脑什么水平?神威?
单纯100个>=0的数和为100的数量(考虑顺序)C(199,99):
45274257328051640582702088538742081937252294837706668420660


悟得 发表于 2020-11-23 10:35:52
szzejz 发表于 2020-11-21 21:46
你好,我也查过可以利用递归,但我不知道应该怎么设计这个递归呢?

1. 你现在的循环是列出所有的情况,其中包含不合适的情况。递归只会列出合适的情况。所以至少有减少一大半的废排列。

2. 对于整个题描述为A(n,N0),当第一个数安排为x时,后面的问题就是A(n-x,N0-x)。x的范围是你能从题干里读到的,比如n个数都是非零正整数。x就是1:N0-n+1。

3. A的规则:反正你又不要一共多少种,只要输出排列,你只需要保证确定某个数时,保证后续的全排1也能保证总和不超过n0就行。另外,你的每一步都是满足N0-xi。只要保证前面x范围取得准,不越域,最后一步执行完出来的排列一定是符合要求的

*4. 建议:这种方法对于n个数和等于n0写起来要容易些。小于n0可能会彼此重复,暂时我也没细想。我建议直接就当n个数等于N0写,然后迭代完令N0=N0-1再一次。只是建议,可行性你自行探索吧。

*5. 【这条不一定对,我没试,只是看到题想到类似得】提醒A的规则好像全排列情况只需要考虑一个不为1就行(x 1 1 1 1 1 3 1 1 1与x 3  1 1 1 1 1 1 1 1 1 1)这种,取x得迭代得时候会把情况遍历全应该。规则应该也很简单,所以我看到就觉得是迭代。自己多试试,这玩意得动手。你动手试完再把遇到得小问题分解拿出来问,这样别人会给你解答。不可能别人整道题给你做。祝好~
您需要登录后才可以回帖 登录 | 注册

本版积分规则

相关帖子
热门教程
站长推荐
快速回复 返回顶部 返回列表