使用精确值打印1和2的所有路径 [英] Print All Paths of 1's and 2's with an Exact Value

问题描述

你好 -



我正在尝试打印出所有可能的1和2路径，这些路径加起来就是一个特定的数字。因此，如果我要3，它将输出1,1,1 1,2和2,1。我尝试了两种递归方法（对我来说根本不起作用）和迭代方法，我有更多的运气。



我在做的是如果数字是3，我首先用1,1,1（1 + 1 + 1 = 3）填充第一行。然后，我遍历第一行的字符，组合1,1的任何单个条目。因此迭代将产生2,1（结合第一个和第二个1）。然后我回去再试一次，增加第一行中字符的索引（依此类推到第二行）。通过并查看第二个和第三个1，并用2替换它们，从而给我一个1,2。这适用于少数。



第一次迭代的结果是：

1,1,1,1,1， 1,1

2,1,1,1,1,1

1,2,1,1,1,1

1 ，1,2,1,1,1

1,1,1,2,1,1

1,1,1,1,2,1

1,1,1,1,1,2



在我到达第一行的末尾后，我增加到第二行（2,1,1,1,1,1）并继续。我寻找下一组1,1并替换为2.在这个例子中，这将给我2,2,1,1,1。进一步的迭代导致：



2,2,1,1,1

2,1,2,1,1
2,1,1,2,1

2,1,1,1,2



还是不错的。在我到达前一组中的最后一个后，我增加到系列中的下一行（1,2,1,1,1,1）。我得到以下内容。虽然有重复。我错过了这个模式。



1 1 1 1 1 1

2 1 1 1 1 1

1 2 1 1 1 1

1 1 2 1 1 1

1 1 1 2 1

1 1 1 1 2 1

1 1 1 1 1 2

2 2 1 1 1

2 1 2 1 1

2 1 1 2 1

2 1 1 1 2

1 2 2 1 1

1 2 1 2 1

1 2 1 1 2

1 1 2 2 1

1 1 2 1 2（这里似乎很好......？）

1 2 2 1 1（这是第12行的副本）

1 1 1 2 2

1 2 1 2 1（这是第13行的副本）

1 1 2 2 1

1 2 1 2 1（这是第13行的副本）



我不确定如果没有代码，你将无法提供帮助。这是否有意义，任何人都可以帮忙吗？



谢谢，

John

Hello-

I am trying to print out all possible paths of 1 and 2 that add up to a specific number. So if I am going for 3, it would output 1,1,1 1,2 and 2,1. I have tried both recursive methodologies (which didn't work at all for me) and an iterative approach, which I am having more luck.

What I am doing is if the number is 3, I start by filling the first line with 1,1,1 (1+1+1=3). Afterwards, I traverse though the characters of the first line, combining any single entry of 1,1. So the iteration would result with 2,1 (combining the first and second 1's). Then I go back and try again, incrementing the index of the character in the first line (so on to the second 1). That goes through and looks at the second and the third 1's, and replaces them with a 2, thus giving me a 1,2. This works for small numbers.

The result for 7 for the first iteration is:
1,1,1,1,1,1,1
2,1,1,1,1,1
1,2,1,1,1,1
1,1,2,1,1,1
1,1,1,2,1,1
1,1,1,1,2,1
1,1,1,1,1,2

After I get to the end of the first line, I increment to the second line (2,1,1,1,1,1) and continue. I look for the next set of 1,1 and replace with a 2. In the example, that would give me 2,2,1,1,1. Further iterations result in:

2,2,1,1,1
2,1,2,1,1
2,1,1,2,1
2,1,1,1,2

Still good. After I get to the last 2 in the previous set, I increment to the next line in the series (1,2,1,1,1,1). I get the following. There are duplicates though. I am missing the pattern.

1 1 1 1 1 1 1
2 1 1 1 1 1
1 2 1 1 1 1
1 1 2 1 1 1
1 1 1 2 1 1
1 1 1 1 2 1
1 1 1 1 1 2
2 2 1 1 1
2 1 2 1 1
2 1 1 2 1
2 1 1 1 2
1 2 2 1 1
1 2 1 2 1
1 2 1 1 2
1 1 2 2 1
1 1 2 1 2 (Seems good up to here...?)
1 2 2 1 1 (This is a duplicate of the 12th line)
1 1 1 2 2
1 2 1 2 1 (This is a duplicate of the 13th line)
1 1 2 2 1
1 2 1 2 1 (This is a duplicate of the 13th line)

I am not sure you would be able to help without the code. Does this make sense and can anyone help?

Thanks,
John

推荐答案

1 2 2 1 1 (This is a duplicate of the 12th line)

应阅读

should read

1 1 1 2 2

之后，没有其他方法可以获得7位五位数。您应该检查4个字符的版本（2221等）。

After that, there is no other way to get a value of 7 with five digits. You should check for the 4-characters versions (2221 etc.).

这与我去年做的类似，我忘记了为什么*，但它可能是对一个问题的回答在这里。



我建议你认识到你总是从 n 1开始（我看到的） （你）和之间你有1个操作符（逗号和加号）。

然后，这个技术是用加号系统地替换逗号。



我做的是使用整数作为位图，指示哪些运算符是逗号，哪些是加号。

在你的情况下，你想要避免两个1位彼此相邻的值。

That's similar to something I did last year, I have forgotten why*, but it was probably in response to a question on here.

What I suggest is to recognize that you always start out with n 1s (as I see you do) and that between the 1s you have operators (commas and plus signs).
The technique, then, is to systematically replace the commas with plus signs.

What I did was to use an integer as a bitmap that indicated which operators are commas and which are plus signs.
In your case, you want to avoid values with two 1-bits beside each other.

Value Bitmap Result
0     00     { 1 , 1 , 1 }
1     01     { 1 , 1 + 1 }
2     10     { 1 + 1 , 1 }
3     11     { 1 + 1 + 1 } Invalid, due to consecutive bits set

算法是从 0 到<$ c $的简单迭代c> 2 ^（n-1）（我仍需要验证）并为每个值迭代这些位以确定结果。





（没有 2s。：D）



*啊，发现它：< a href =http://www.codeproject.com/Messages/4916409/Friday-Programming-Challenge.aspx> http://www.codeproject.com/Messages/4916409/Friday-Programming-Challenge.aspx [ ^ ]

您只使用整体和半部来描述节奏。

The algorithm is a simple iteration from 0 to 2^(n-1) (I still need to verify that) and for each value you iterate the bits to determine the result.


(There are no 2s. :D )

* Ah, found it: http://www.codeproject.com/Messages/4916409/Friday-Programming-Challenge.aspx[^]
You describe "rhythms" using only wholes and halves.

这篇关于使用精确值打印1和2的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！