有些时候使用数字进行遍历,然后将数字转化成需要的进制数,再将进制数对应成需要的字符是一种非常有效的方法。
如:
输入一个正整数X,在下面的等式左边的数字之间添加+号或者-号,使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如:
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序,统计满足输入整数的所有整数个数。
输入: 正整数,等式右边的数字
输出: 使该等式成立的个数
样例输入:5
样例输出:21
结题思路:每两个数字之间的空格都有三种选项:+/-/空,"空"代表不加符号。
将所有数字的符号用一个三进制的数来表示,用1代表+,2代表-,0代表空。10000021,就代表1+2 3 4 5 6 7-8+9
所以,按照三进制的话从0到22222222就可以代表所有的结果的可能了,转换成十进制就是从0到6560。
下面程序中要注意,要遍历的数转换成三进制的字符串的长度小于8的时候需要在前面补0。
1 #include<iostream>
2 #include<ctype.h>
3 #include<string>
4 using namespace std;
5 string to3(int num)
6 {
7 string str;
8 char c[100];
9 itoa(num,c,3);
10 str=c;
11 if(str.length()<8)
12 {
13 str.insert(0,8-str.length(),'0');
14 }
15 return str;
16 }
17 int main()
18 {
19 int N;
20 cin>>N;
21 int count=0;
22 string snum="123456789";
23 //1+ 2- 0空格
24 for(int num=0;num<6561;num++)
25 {
26 string str=to3(num);
27 string ::iterator it=snum.begin();
28 string rstr;
29 for(int i=0;i<8;i++)
30 {
31 rstr.push_back(snum[i]);
32 if(str[i]=='1')
33 {
34 rstr.push_back('+');
35 }
36 else if(str[i]=='2')
37 {
38 rstr.push_back('-');
39 }
40 }
41 rstr.push_back(snum[8]);//rstr已经变成12+3-4+567-89的格式
42 int len=rstr.length();
43 int num[9];
44 int n=0;
45 string::iterator p1,p2;
46 p1=p2=rstr.begin();
47 string fuhao;
48 while(p1!=rstr.end())
49 {
50 while(p1-rstr.begin()<len &&isdigit(*p1))
51 {
52 p1++;
53 }
54 if(p1!=rstr.end()&&(*p1=='+'||*p1=='-'))
55 {
56 fuhao.push_back(*p1);
57 }
58 string s_num=rstr.substr(p2-rstr.begin(),p1-p2);
59 num[n++]=atoi(s_num.c_str());
60 if(p1<rstr.end())
61 {
62 p1++;
63 p2=p1;
64 }
65
66 }
67 int sum=num[0];
68 for(int i=0;i<n-1;i++)
69 {
70 if(!fuhao.empty())
71 {
72 if(fuhao[i]=='+')
73 {
74 sum=sum+num[i+1];
75 }
76 if(fuhao[i]=='-')
77 {
78 sum=sum-num[i+1];
79 }
80 }
81 }
82 if(sum==N)
83 {
84 count++;
85 }
86
87 }
88 cout<<count;
89 return 0;
90 }