c++ - 如何编写程序来生成以下模式？

问题描述

你可以使用递归，循环，向量或字符串都没有关系。

给定输入 N 将生成 N 行模式。

编辑：我想出了如何进行预计算。可以一次一步迭代地进行吗？

void per(vector<int> v, int value) {

    cout << v;
    if (v.size() == value) {
        return;
    }

    if(v.back() < value && v.size() < value) {
        vector<int> modified(v);
        for(int i = 0; i < modified.size(); i++) {
            modified[i] += 1;
        }
        per(modified, value);
    }

    if(v.back() < value && v.size() < value) {
        // for(int i = 0; i < value; i++) {
        vector<int> modified(v);
        modified.push_back(modified.back() + 1);
        per(modified, value);
    }


}

您如何看待这样的递归算法。我试图绘制输出树，但很糟糕。也许这样的问题不适合递归。似乎它应该是递归的，并且其中包含问题的最小子集。

标签： c++algorithmrecursion

有一个迭代解决方案，涉及在迭代时遍历i先前添加的以开头的模式j，其中 j 从 1 变为i-1，然后添加i。

下面是一些 Java 代码来说明：

static List<String> pattern(int n)
{
    List<String> res = new ArrayList<>();
    
    for(int i=1; i<n; i++)
    {
        res.add(String.valueOf(i));
        
        for(int j=1; j<i; j++)
        {
            int size = res.size();
            for(int k=0; k<size; k++)
                if(res.get(k).equals(String.valueOf(j)) || 
                        res.get(k).startsWith(String.valueOf(j) + " "))
                {
                    res.add(res.get(k) + " " + i);
                }
        }
    }
    return res;
}

测试：

for(String s : pattern(5)) System.out.println(s);

输出：

可能有一种更聪明的方法涉及递归，避免必须遍历先前添加的模式并检查第一个字符，但我还没有看到它。

编辑：

请注意，一旦数字开始变成多位数字，上面的原始版本就会出现问题 - 例如startsWith(1)开始匹配10。我已经更新了代码来解决这个问题。

在玩了一段时间之后，我确实设法提出了一个我觉得更令人满意的解决方案，它使用迭代和递归的组合来生成每个给定级别的条目列表。但这并不简单。

static List<String> pattern(int n)
{
    List<String> res = new ArrayList<>();
    
    for(int i=1; i<=n; i++)
    {
        res.add(String.valueOf(i));
        
        for(int j=1; j<i; j++)              
            for(String s : list(i-1, j)) 
                res.add(String.format("%s %d", s, i));
    }
    
    return res;
}

static List<String> list(int i, int j)
{
    if(i == j) 
        return new ArrayList<>(Arrays.asList(String.valueOf(j)));
                    
    List<String> a = list(i-1, j);      
    for(int k=0, s=a.size(); k<s; k++) 
        a.add(String.format("%s %d", a.get(k), i));
    return a;
}

和一个 Javascript 版本。

function list(i, j) {
    if(i === j) return [j];
  
  let a = list(i-1, j);
  a.forEach(s => a.push(s + ' ' + i));
  return a;
}

function gen(n) {
    let res = []
  
  for(let i=1; i<=n; i++) {
    res.push(i.toString());
    for(let j=1; j<i; j++) {
      list(i-1, j).forEach(s => res.push(s + ' ' + i));
    }
  }
    
  return res
}

gen(4).forEach(_ => console.log(_));

c++ - 如何编写程序来生成以下模式？

问题描述

解决方案

推荐阅读