仅使用递归将数字从 1 设置为所选数字 [英] Setting numbers from 1 to chosen number using recursion only

问题描述

连续大约 7 小时后，我真的需要一些帮助，我需要从递归返回选项数量，可以通过将数字从 1 设置为所选数字(最大数字)，这是禁止使用循环/数组，只有递归，数字都是正数(大于 0)并且只会更正数，例如:好的一个:{1,2}，坏的一个:{2,1}.

After about 7 hours in a row I really need some help , I need to return from recursion the amount of options that can be by setting numbers from 1 to chosen number(maximum number) , it's forbidden to use loops/arrays , only recursion , the numbers are all positive(more than 0) and goes only more positively , example : good one : {1,2} , bad one : {2,1}.

示例:

n = 3 , max = 2 

n : 应该在行中的数字, max : 行中的最大数目.

n : The numbers that should be in the row , max : The maximum number that can be in the row.

{1,1,1}
{1,1,2}
{1,2,2}
{2,2,2}

从该示例中应该返回 4，因为有 3 个数字的 4 个选项，它们的值最大为 2.

from that example that should return 4 because there are 4 options of 3 numbers that their value is maximum 2.

另一个:

n=2
max=3

{1,1}
{1,2}
{1,3}
{2,2}
{2,3}
{3,3}

从那个例子中它应该返回 6，因为有 6 个选项.

from that example it should return 6 because there are 6 options.

推荐答案

如果没有先验知识，即使对于有经验的数学家来说，这也可能是一个具有挑战性的问题.它是 multisets 的计数，这是组合学的基本构建块之一.我将解释我对维基百科中递归关系思想的理解.

Without prior knowledge, this would probably be a challenging question even for an experienced mathematician. It is the count of multisets, one of the fundamental building blocks in combinatorics. I'll explain my understanding of the idea for the recurrence relation in Wikipedia.

通常 k 用于多集基数(您的问题称为 n)，而 n 用作要从中选择的集合(不是多重集合)(您问题中的 max).

Typically k is used for the multiset cardinality (what your question refers to as n), while n is used as the cardinality of the set (not multiset) to choose from (the max in your question).

对于f(n, k)，基本情况是:

f(n, 0) = 1
one way to fill the empty multiset

还有，

f(0, k) = 0
no ways to choose from an empty set

对于常规情况，我们考虑第 n 个元素(来自选择集).我们想计算包含它的所有组合以及所有缺少它的组合.在没有 nth 元素的情况下计算所有组合很容易:我们将相同的多集计数函数应用于 k，但少了一个选择:

For the regular case, we consider the nth element (from the set of choices). We'd like to count all the combinations that include it and all those where it's missing. Counting all combinations without the nth element is easy: we have the same multiset counting function applied to k with one less choice:

f(n - 1, k)

现在要计算包含至少一个 n 元素的组合，我们想象一下从 n 项中进行选择的所有方式(其中一些将不包括nth 个元素)但在每个组合中保存一个位置，我们将在其中放置 n 个元素，所以我们最终得到:

Now to count the combinations that include at least one nth element, we imagine taking all the ways of choosing from n items (some of which will not include an nth element) but saving one place in each combination where we will place an nth element, so we end up with:

f(n, k - 1)

综合起来:

function f(n, k){
  if (n == 0)
    return 0;
  if (k == 0)
    return 1;

  return f(n - 1, k) + f(n, k - 1);
}

console.log(f(2, 3));
console.log(f(3, 2));

这篇关于仅使用递归将数字从 1 设置为所选数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！