jjzjj

c++ - 乐高塑料积木的组合数 C++

coder 2024-01-31 原文

您有一些乐高塑料积木，所有积木都是 1x1x1。您还有一 block 瓷砖，1xN(N <= 80)，您应该在上面放置乐高积木。您可以按顺序排列它们(如果有="" 3="" 个或更多连续的积木，则一个序列是正确的)，而且您必须在="" 2="" 个序列之间至少有="" 1="" 个空格。您应该计算可以将砖="" block="">

这是一个例子:

如果图 block 是 1x7，则有 17 种不同的组合。

输入:7 输出:17


(来源:mendo.mk)

此外，如果您没有积木，则计为 1 种组合。

我已经研究过这个问题，并且找到了计算图 block 的最大长度是否为 14(3 个序列)的可能组合的方法。我发现它使用 for 循环。

我最大的问题是我需要运行大量的 for 循环。例如，对于 1 个序列，我使用 1 个 for 循环，对于 2 个序列，2 个循环 + 1 个用于 1 个序列...所以如果我使用所有 80 个积木，我可以创建 20 个序列，我将不得不使用超过 210 个 for 循环，这是数量巨大。所以如果我能把它们嵌套在一起就好了。我试过了，它变得很乱，而且没有给出正确的答案。

新代码:

#include <iostream>
using namespace std;
int main()
{
    long long int places, combinations = 1;
    cin >> places;
    long long int f[80], g[80];
    f[0] = 0;
    f[1] = 0;
    f[2] = 0;
    g[0] = 1;
    g[1] = 1;
    g[2] = 1;
    for(int i = 3; i<=places; i++)
    {
        f[i] = f[i-1] + g[i-3];
        g[i] = f[i-1] + g[i-1];
    }
    combinations = f[places] + g[places];
    cout << combinations;
    return 0;
}

最佳答案

如果这是一个计数问题(不是输出组合，而只是计算它们)，这是一个简单的问题。假设我们现在对 n ≥ 3 求解它对 n+1 求解，我们通过归纳求解:

假设 f 是一个函数，它显示使最后一项成为砖 block 的可能方式的数量。 类似地，g 是一个函数，它显示了使最后一项不是砖 block 的可能方式的数量。 让定义 h = f+g，作为所有可能方式的数量。

所以我们有:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

有初始条件:

for n=0,1,2: g=1, f= 0.
for n = 3: g=1,f=1

示例:

n=4: g=2,f=2 ==> h=4
n=5: g=4, f= 3 ==> h=7
n=6: g=7, f= 4 ==> h=11
n=7: g=11,f=6 ==> h=17

我们可以用 O(n) 中的一个 for 循环解决它。

为什么:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

首先，让我们证明第一部分:

请记住，我们假设 f(n) 是最后一项有塑料砖的工作解决方案，而 g(n) 是最后一项没有砖的工作解决方案。

f(n+1) 可以通过在最后一个地方添加一 block 砖从 f(n) 获得。 同样f(n+1)可以在g(n-2)后加三 block 砖得到，即n-1,n,n+1的单元格。

请注意，我们不能在 g(n-1) 或 g(n) 之后添加砖 block 来创建 f(n+1) 的有效解决方案，因为它们不是有效解决方案(连续砖 block 的数量少于 3 ).另外，请注意，我们不需要计算在 g(n-3) 之后添加砖 block 所产生的路数，因为它们之前已由 f(n) 枚举。所以我们有 f(n+1) = f(n) + g(n-2)。

以同样的方式我们可以证明 g(n+1) = f(n)+g(n) 这种情况更容易，因为 g(n+1) 可以简单地由直到 n 的任何有效解决方案，因为这里没有 3 个连续的砖 block 障碍，它们可以在任何有效解决方案之后出现。

关于c++ - 乐高塑料积木的组合数 C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10396058/

amp积木codeblockc++algorithmloopscombinationslego-mindstorms

有关c++ - 乐高塑料积木的组合数 C++的更多相关文章

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

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

  2. 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.你能做的最好的事情是:

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. ruby - 最多 n 的组合 - 2

    给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我

  5. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  6. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  7. ruby - Rails 组合多个 activerecord 关系 - 2

    我想合并多个事件记录关系例如，apple_companies=Company.where("namelike?","%apple%")banana_companies=Company.where("namelike?","%banana%")我想结合这两个关系。不是合并，合并是apple_companies.merge(banana_companies)=>Company.where("namelike?andnamelike?","%apple%","%banana%")我要Company.where("名字像？还是名字像？","%apple%","%banana%")之后，我会写代

  8. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  9. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

    我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

  10. ruby - 如何在 ruby 中组合/排列？ - 2

    我有一个熟悉的问题，看起来像是数学世界的排列/组合。如何通过ruby​​实现以下目标？badges="1-2-3"badge_cascade=[]badges.split("-").eachdo|b|badge_cascade["1","2","3"]ButIwantittobeis:=>["1","2","3","1-2","2-3","3-1","2-1","3-2","1-3","1-2-3","2-3-1","3-1-2"] 最佳答案 函数式方法:bs="1-2-3".split("-")strings=1.upto(bs.

随机推荐