草庐IT

c++ - 递归函数计数和打印 1 到 n-1 的分区

coder 2024-02-25 原文

我正在尝试编写一个递归函数(它必须是递归的)来打印出 1 到 n-1 的分区和分区数。 例如，总和为 4 的 4 个组合:

1 1 1 1
1 1 2
1 3
2 2

我只是在使用该功能时遇到了很多麻烦。下面这个功能不起作用。有人可以帮帮我吗？

 int partition(int n, int max)
{

  if(n==1||max==1)
    return(1);
  int counter = 0;
  if(n<=max)
    counter=1;
  for(int i = 0; n>i; i++){
          n=n-1;
          cout << n << "+"<< i <<"\n";
          counter++;
          partition(n,i);         
        }

  return(counter);
}

最佳答案

这是解决您的问题的良好开端:

#include <stdlib.h>
#include <stdio.h>

void partition(int n, int sum, int *summands, int num_summands)
{
  int i;

  if (sum == n)  // base case of recursion
  {
    if (num_summands > 1)  // don't print n by itself
    {
      for (i = 0; i < num_summands; ++i)
        printf("%d ", summands[i]);

      printf("\n");
    }
  }
  else
  {
    /* TODO: fill in recursive case */
    /* Iteratively recurse after appending one additional, varying summand to summands */
    /* It might be easier to first generate all permutations of the sums */
    /* and then figure out how to reduce that down to only the unique sets of summands (think sorting) */
  }
}

int main(int argc, char **argv)
{
  if (argc == 1)
  {
    printf("usage: %s <num>; where num > 1\n", argv[0]);
    return 1;
  }

  int n = atoi(argv[1]);

  if (n <= 1)
  {
    printf("usage: %s <num>; where num > 1\n", argv[0]);
    return 1;
  }

  int summands[n+1];               // NOTE: +1's are to make summands[-1] always safe inside recursion

  summands[0] = 1;                 // NOTE: make summands[-1] == 1 at top level of recursion
  partition(n, 0, summands+1, 0);  // NOTE: +1's are to make summands[-1] always safe inside recursion

  return 0;
}

如果您需要对找到的总和进行计数，则可以向 partition 添加一个额外参数，该参数是一个指向 (int) 到目前为止找到的总和计数的指针。您只会在打印基本案例中增加该计数。在 main 中，您将传递一个指向零初始化整数的指针，而在递归中，您只需传递指针。当您返回 main 时，您可以打印找到的总和数。

关于c++ - 递归函数计数和打印 1 到 n-1 的分区，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28891477/

amp43summandsintsectionc++recursionpartition

有关c++ - 递归函数计数和打印 1 到 n-1 的分区的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  3. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容？ - 2

    我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

  4. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  5. Ruby rpartition 与分区？ - 2

    rpartition和partition有什么区别？我已经阅读了文档，但我认为它们是一样的。只是那些出现在后来的ruby​​版本中吗？ 最佳答案 以下示例将有助于识别差异:"abccba".partition("b")#=>["a","b","ccba"]"abccba".rpartition("b")#=>["abcc","b","a"]所以区别在于rpartition搜索最右边的匹配项，而不是最左边的匹配项。 关于Rubyrpartition与分区？，我们在StackOverflow

  6. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  7. ruby-on-rails - Ruby on Rails 计数器缓存错误 - 2

    尝试在我的RoR应用程序中实现计数器缓存列时出现错误Unknownkey(s):counter_cache。我在这个问题中实现了模型关联:Modelassociationquestion这是我的迁移:classAddVideoVotesCountToVideos0Video.reset_column_informationVideo.find(:all).eachdo|p|p.update_attributes:videos_votes_count,p.video_votes.lengthendenddefself.downremove_column:videos,:video_vot

  8. ruby - 使用多个数组创建计数 - 2

    我正在尝试按0-9和a-z的顺序创建数字和字母列表。我有一组值value_array=['0','1','2','3','4','5','6','7','8','9','a','b'，'光盘'，'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','','u','v','w','x','y','z']和一个组合列表的数组，按顺序，这些数字可以产生x个字符，比方说三个list_array=[]和一个当前字母和数字组合的数组(在将它插入列表数组之前我会把它变成一个字符串，]current_combo['0','0','0']

  9. ruby - 在 Ruby 中按名称传递函数 - 2

    如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

  10. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

随机推荐