使用数字进行字符遍历

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

如:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P2181 对角线(组合数)

题目描述 对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: ? 输入输出格式 输入格式: 第一行一个...

36050
来自专栏数据结构与算法

P3372 【模板】线段树 1 区间查询与区间修改

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式: 第一行包含两个...

32360
来自专栏机器学习算法工程师

算法题系列之二:求最大子数组之积

题目描述: 给定一个长度为N的整数数组,只允许用乘法,计算任意(N-1)个数的组合中乘积最大的一组。 算法分析: 动态规划的做法,假设数组为a[N],ma...

28660
来自专栏PHP在线

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

45180
来自专栏程序生活

最大连续子序列和

https://blog.csdn.net/bitcarmanlee/article/details/51526010

10820
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

30870
来自专栏nummy

numpy入门

numpy中最主要的对象是同质数组array,也就是说数组中的元素类型都是一样的。数组的维度也称之为axis,axis的的个数称之为秩rank。

12720
来自专栏猿人谷

C语言函数指针基础

本文写的非常详细,因为我想为初学者建立一个意识模型,来帮助他们理解函数指针的语法和基础。如果你不讨厌事无巨细,请尽情阅读吧。 函数指针虽然在语法上让人有些迷惑,...

431100
来自专栏小L的魔法馆

C++继承与多态练习--计算图形面积

44390
来自专栏WD学习记录

牛客网 数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的...

13630

扫码关注云+社区

领取腾讯云代金券