使用数字进行字符遍历

用户1215536

发布于 2018-02-05 14:41:05

1.3K0

发布于 2018-02-05 14:41:05

文章被收录于专栏：软件开发 -- 分享互助成长软件开发 -- 分享互助成长

有些时候使用数字进行遍历，然后将数字转化成需要的进制数，再将进制数对应成需要的字符是一种非常有效的方法。

如：

输入一个正整数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 }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2015-04-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法