C++:在新基础上生成组合
C++: Generate combinations in new base
我试图在一个由给定字母表指定的新基数中进行计数。所以对于以下参数:
#define ALPHABET "abc"
#define ALPHABET_LEN 3
我会得到以下结果:
0 | a
1 | b
2 | c
3 | aa
4 | ab
...
9 | ca
10| cb
我已尝试使用以下代码执行此操作:
#include <iostream>
#include <string>
#define ALPHABET "abc"
#define ALPHABET_LEN 3
int main()
{
for (int i = 0; i <= 10; i++) {
int l = 0;
int n_ = i;
int n = i;
char secret[4];
while (n > 0) {
secret[l] = ALPHABET[n%ALPHABET_LEN];
n /= ALPHABET_LEN;
l++;
}
std::cout << i << " | " << secret << std::endl;
}
}
不幸的是,这会打印以下内容:
0 |
1 | b
2 | c
3 | ab
4 | bb
5 | cb
6 | ac
7 | bc
8 | cc
9 | aab
10 | bab
这不是预期的模式。我该如何解决这个问题,有没有比使用 mod?
剥离下一个字符更好的方法
int i = 0;
int n = i;
while (n > 0) {
显然,在第一次迭代中,内部循环不会 运行 一次迭代,因此 secret
不会包含它应该包含的 a
。
P.S。您未能以 null 终止 secret
,因此当您将程序插入输出流时程序的行为未定义。
这是一个具有挑战性的算法问题。问题描述具有误导性。基础转换表明将有一个 'zero' 值,类似于这样:
a、b、c、a0、aa、ab、ac、b0、b1、b2、c0 等
但是,在这道题中,'a'表示'zero',但'a'也是第一个数字
将此视为基础转换会产生复杂的兔子洞。
相反,必须弄清楚计算每个连续数字的算法,而忽略碱基转换的想法。
第一种方法是为每个数字得出一个公式,如下所示:
int LEN = ALPHABET_LEN; // Use a shorter variable name
std::string = ALPHABET[i % LEN]; // first digit
if(i > LEN - 1) {
secret = ALPHABET[(i/LEN -1)%LEN] + secret;
}
if(i > LEN * (LEN+1) - 1) {
secret = ALPHABET[(i/(LEN *(LEN+1)) - 1)%LEN] + secret;
}
if(i > LEN * (LEN+1) *(LEN+1) - 1) {
secret = ALPHABET[(i/(LEN *(LEN+1) * (LEN+1) ) - 1)%LEN] + secret;
}
当您计算出每个连续数字的公式时,您会意识到底数实际上是 LEN+1 而不是 LEN。
这种方法有效,但它总是需要为每个连续的数字添加一个额外的 if 语句。当然,对于 i = 1 .. 10,这工作正常。但是如果我 = 10,000,000 呢?这将需要无穷无尽的连续系列 if 语句。
但是,在发现模式之后,现在创建一个 while() 语句会更容易一些,它避免了对无休止的一系列 if 语句的需要。
#include <iostream>
#include <string>
//works as #define, but I like string so I can easily test with
// longer strings such as "abcd"
std::string ALPHABET {"abc"};
int main()
{
const int LEN = ALPHABET.size(); // Shorten the var name
for (int i = 0; i <= 100; i++) { // use i <= 100 to verify the algorithm
int number = i; // save the number that we are working on for this row
std::string secret = "";
secret += ALPHABET[i % LEN];
while(number / LEN > 0){
number = number/LEN - 1; // the base is really 4 rather than 3
secret = ALPHABET[number%LEN] + secret;
}
std::cout << i << " | " << secret << std::endl;
}
}
输出将是:
0 | a
1 | b
2 | c
3 | aa
4 | ab
5 | ac
6 | ba
7 | bb
8 | bc
9 | ca
10 | cb
11 | cc
12 | aaa
13 | aab
14 | aac
15 | aba
16 | abb
17 | abc
18 | aca
19 | acb
20 | acc
21 | baa
22 | bab
23 | bac
24 | bba
25 | bbb
26 | bbc
27 | bca
28 | bcb
29 | bcc
30 | caa
31 | cab
32 | cac
33 | cba
34 | cbb
35 | cbc
36 | cca
37 | ccb
38 | ccc
39 | aaaa
40 | aaab
41 | aaac
42 | aaba
43 | aabb
44 | aabc
45 | aaca
46 | aacb
47 | aacc
48 | abaa
49 | abab
50 | abac
51 | abba
52 | abbb
53 | abbc
54 | abca
55 | abcb
56 | abcc
57 | acaa
58 | acab
59 | acac
60 | acba
61 | acbb
62 | acbc
63 | acca
64 | accb
65 | accc
66 | baaa
67 | baab
68 | baac
69 | baba
70 | babb
71 | babc
72 | baca
73 | bacb
74 | bacc
75 | bbaa
76 | bbab
77 | bbac
78 | bbba
79 | bbbb
80 | bbbc
81 | bbca
82 | bbcb
83 | bbcc
84 | bcaa
85 | bcab
86 | bcac
87 | bcba
88 | bcbb
89 | bcbc
90 | bcca
91 | bccb
92 | bccc
93 | caaa
94 | caab
95 | caac
96 | caba
97 | cabb
98 | cabc
99 | caca
100 | cacb
Process finished with exit code 0
我试图在一个由给定字母表指定的新基数中进行计数。所以对于以下参数:
#define ALPHABET "abc"
#define ALPHABET_LEN 3
我会得到以下结果:
0 | a
1 | b
2 | c
3 | aa
4 | ab
...
9 | ca
10| cb
我已尝试使用以下代码执行此操作:
#include <iostream>
#include <string>
#define ALPHABET "abc"
#define ALPHABET_LEN 3
int main()
{
for (int i = 0; i <= 10; i++) {
int l = 0;
int n_ = i;
int n = i;
char secret[4];
while (n > 0) {
secret[l] = ALPHABET[n%ALPHABET_LEN];
n /= ALPHABET_LEN;
l++;
}
std::cout << i << " | " << secret << std::endl;
}
}
不幸的是,这会打印以下内容:
0 |
1 | b
2 | c
3 | ab
4 | bb
5 | cb
6 | ac
7 | bc
8 | cc
9 | aab
10 | bab
这不是预期的模式。我该如何解决这个问题,有没有比使用 mod?
剥离下一个字符更好的方法int i = 0;
int n = i;
while (n > 0) {
显然,在第一次迭代中,内部循环不会 运行 一次迭代,因此 secret
不会包含它应该包含的 a
。
P.S。您未能以 null 终止 secret
,因此当您将程序插入输出流时程序的行为未定义。
这是一个具有挑战性的算法问题。问题描述具有误导性。基础转换表明将有一个 'zero' 值,类似于这样:
a、b、c、a0、aa、ab、ac、b0、b1、b2、c0 等
但是,在这道题中,'a'表示'zero',但'a'也是第一个数字
将此视为基础转换会产生复杂的兔子洞。
相反,必须弄清楚计算每个连续数字的算法,而忽略碱基转换的想法。
第一种方法是为每个数字得出一个公式,如下所示:
int LEN = ALPHABET_LEN; // Use a shorter variable name
std::string = ALPHABET[i % LEN]; // first digit
if(i > LEN - 1) {
secret = ALPHABET[(i/LEN -1)%LEN] + secret;
}
if(i > LEN * (LEN+1) - 1) {
secret = ALPHABET[(i/(LEN *(LEN+1)) - 1)%LEN] + secret;
}
if(i > LEN * (LEN+1) *(LEN+1) - 1) {
secret = ALPHABET[(i/(LEN *(LEN+1) * (LEN+1) ) - 1)%LEN] + secret;
}
当您计算出每个连续数字的公式时,您会意识到底数实际上是 LEN+1 而不是 LEN。
这种方法有效,但它总是需要为每个连续的数字添加一个额外的 if 语句。当然,对于 i = 1 .. 10,这工作正常。但是如果我 = 10,000,000 呢?这将需要无穷无尽的连续系列 if 语句。
但是,在发现模式之后,现在创建一个 while() 语句会更容易一些,它避免了对无休止的一系列 if 语句的需要。
#include <iostream>
#include <string>
//works as #define, but I like string so I can easily test with
// longer strings such as "abcd"
std::string ALPHABET {"abc"};
int main()
{
const int LEN = ALPHABET.size(); // Shorten the var name
for (int i = 0; i <= 100; i++) { // use i <= 100 to verify the algorithm
int number = i; // save the number that we are working on for this row
std::string secret = "";
secret += ALPHABET[i % LEN];
while(number / LEN > 0){
number = number/LEN - 1; // the base is really 4 rather than 3
secret = ALPHABET[number%LEN] + secret;
}
std::cout << i << " | " << secret << std::endl;
}
}
输出将是:
0 | a
1 | b
2 | c
3 | aa
4 | ab
5 | ac
6 | ba
7 | bb
8 | bc
9 | ca
10 | cb
11 | cc
12 | aaa
13 | aab
14 | aac
15 | aba
16 | abb
17 | abc
18 | aca
19 | acb
20 | acc
21 | baa
22 | bab
23 | bac
24 | bba
25 | bbb
26 | bbc
27 | bca
28 | bcb
29 | bcc
30 | caa
31 | cab
32 | cac
33 | cba
34 | cbb
35 | cbc
36 | cca
37 | ccb
38 | ccc
39 | aaaa
40 | aaab
41 | aaac
42 | aaba
43 | aabb
44 | aabc
45 | aaca
46 | aacb
47 | aacc
48 | abaa
49 | abab
50 | abac
51 | abba
52 | abbb
53 | abbc
54 | abca
55 | abcb
56 | abcc
57 | acaa
58 | acab
59 | acac
60 | acba
61 | acbb
62 | acbc
63 | acca
64 | accb
65 | accc
66 | baaa
67 | baab
68 | baac
69 | baba
70 | babb
71 | babc
72 | baca
73 | bacb
74 | bacc
75 | bbaa
76 | bbab
77 | bbac
78 | bbba
79 | bbbb
80 | bbbc
81 | bbca
82 | bbcb
83 | bbcc
84 | bcaa
85 | bcab
86 | bcac
87 | bcba
88 | bcbb
89 | bcbc
90 | bcca
91 | bccb
92 | bccc
93 | caaa
94 | caab
95 | caac
96 | caba
97 | cabb
98 | cabc
99 | caca
100 | cacb
Process finished with exit code 0