[华为机试真题][2014]63.等式变换

题目

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

代码

/*---------------------------------------
*   日期:2015-07-06
*   作者:SJF0115
*   题目:等式变换
*   来源:华为机试真题
-----------------------------------------*/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// 整型转换为字符串
string Int2Str(int num){
    string str;
    if(num == 0){
        str = '0';
        return str;
    }//if
    int tmp = num;
    while(num){
        str.insert(str.begin(),num % 10 + '0');
        num /= 10;
    }//while
    return str;
}

/*
当前计算值              result
符合的等式个数          count
等式结果                x
相邻数合并的结果        sequence    1 + 2 + 345  345 就是 sequence
*/
void helper(vector<int> &num,int index,int x,int result,int sequence,int &count,string op){
    if(index == num.size()){
        if(result + sequence == x || result - sequence == x){
            ++count;
            if(result + sequence == x){
                op += "+"+Int2Str(sequence);
            }//if
            else{
                op += "-"+Int2Str(sequence);
            }//else
            cout<<op<<endl;
        }//if
        return;
    }//if
    // 连续数
    helper(num,index+1,x,result,sequence * 10 + num[index],count,op);

    // 加法 +
    if(op.size() > 0){
        // 以num[index]为sequence的起点
        helper(num,index+1,x,result + sequence,num[index],count,op+"+"+Int2Str(sequence));
    }//if
    else{
        // 以num[index]为sequence的起点
        helper(num,index+1,x,result + sequence,num[index],count,op+Int2Str(sequence));
    }//else

    if(op.size() > 0){
        // 减法-
        // 以num[index]为sequence的起点
        helper(num,index+1,x,result - sequence,num[index],count,op+"-"+Int2Str(sequence));
    }//if
}

int TransformationEquation(vector<int> num,int x){
    int count = 0;
    string op = "";
    helper(num,1,x,0,num[0],count,op);
    return count;
}

int main(){
    int n,x;
    int num;
    //freopen("C:\\Users\\Administrator\\Desktop\\acm.in","r",stdin);
    while(cin>>n>>x){
        vector<int> vec;
        for(int i = 0;i < n;++i){
            cin>>num;
            vec.push_back(num);
        }//for
        cout<<TransformationEquation(vec,x)<<endl;
    }//while
    return 0;
}
时间: 2024-09-19 09:00:32

[华为机试真题][2014]63.等式变换的相关文章

[华为机试真题][2014]64.实现两个合法时间相加

题目 描述: 给定两个合法的时间(格式固定:hh:mm:ss,时间合法,不用考虑其它情况),输入两个时间相加后的结果:注意,相加后的结果也必需是一个合法的时间: 附合法时间定义:小时在[00-23]之间,分钟和秒分别是在[00-59]之间: 运行时间限制: 无限制 内存限制: 无限制 输入: 时分秒格式的时间字符串,如00:00:00 输出: 时分秒格式的时间字符串,如00:00:00 样例输入: 00:00:00 00:00:01 样例输出: 00:00:01 答案提示: 建议将时间转换为秒数

[华为机试真题]70.分苹果

题目 M个相同苹果放到N个相同篮子里有多少种放法,允许有篮子不放. 1<=M<=10,1<=N<=10 例如5个苹果三个篮子,3,1,1 和 1,1,3是同一种放法 输入 7 3 输出 8 思路 设f(m,n) 为m个苹果,n个盘子的放法数目: 当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响.即if(n>m) f(m,n) = f(m,m) 当n<=m:不同的放法可以分成两类: (1)有至少一个盘子空着,即相当于f(m,n) = f(m

[华为机试真题]69.姓名的夫妻相

题目 在中国,形容夫妻恩爱的词汇中,大家用的比较多的就是"夫妻相".所谓"夫妻相",就是两个人看上去比较般配,长相.身材等某些方面有一定的相似度. 本题则另辟蹊径,从人的姓名维度,以字母重复个数来寻找最具"夫妻相"的人. 题目中预先给定一组女士的姓名拼音.输入男士的姓名拼音(拼音中间可以有空格,字母全部小写),依预先给定姓名拼音的先后遍历所有姓名,输出字母重复数最多的女士姓名. 规则1:如果字母重复数最多的女士有多位相同,则以最先匹配的女士做为最

[华为机试真题]72.操作系统任务调度问题

题目 操作系统任务调度问题.操作系统任务分为系统任务和用户任务两种.其中, 系统任务的优先级 < 50,用户任务的优先级 >= 50且 <= 255.优先级大于255的为非法任务,应予以剔除. 现有一任务队列task[],长度为n,task中的元素值表示任务的优先级,数值越小,优先级越高. 函数scheduler实现如下功能: 将task[] 中的任务按照系统任务.用户任务依次存放到 system_task[] 数组和 user_task[] 数组中 (数组中元素的值是任务在task[]

[华为机试真题]68.简单四则运算

题目 输入一个只包含个位数字的简单四则运算表达式字符串,计算该表达式的值 注: 3.1.表达式只含 +, -, *, / 四则运算符,不含括号 3.2.表达式数值只包含个位整数(0-9),且不会出现0作为除数的情况 3.3.要考虑加减乘除按通常四则运算规定的计算优先级 3.4.除法用整数除法,即仅保留除法运算结果的整数部分.比如8/3=2.输入表达式保证无0作为除数情况发生 3.5.输入字符串一定是符合题意合法的表达式,其中只包括数字字符和四则运算符字符,除此之外不含其它任何字符,不会出现计算溢

[华为机试真题]73.公交站寻址

题目 一个N*N二维矩阵代表城市布局,元素值只有'.','X' , 'B' , 'S',X代表当前位置,B代表路障,S代表公交站,'.'代表可行的路径. 现给定路径长度Y,找到能够到达的公交站的个数,路径中不能包含路障. 路径长度定义: 节点与其自身的距离为0 节点与其上.下.左.右四个相邻节点距离都为1 要求实现函数 int FindStat (const char *Map, unsigned int iArrN, unsigned int iPathLen) 输入 Map: 城市布局 iA

[华为机试真题]67.奇偶数入座

题目 代码 /*--------------------------------------- * 日期:2015-07-07 * 作者:SJF0115 * 题目:奇偶数入座 * 来源:华为机试真题 -----------------------------------------*/ #include <iostream> #include <string> #include <vector> #include <stack> #include <a

[华为机试真题][2015]65.和尚挑水

题目 某寺庙里7个和尚:轮流挑水,为了和其他任务不能冲突,各人将有空天数列出如下表: 和尚1: 星期二,四; 和尚2: 星期一,六; 和尚3: 星期三,日; 和尚4: 星期五; 和尚5: 星期一,四,六; 和尚6: 星期二,五; 和尚7: 星期三,六,日; 请将所有合理的挑水时间安排表 思路 回朔法求解 回朔法即每进行一步,都试图在当前部分解的基础上扩大该部分解.扩大时,首先检查扩大后是否违反了约束条件,若不违反,则扩大之,然后继续在此基础上按照类似的方法进行,直至成为完整解:若违反,则放弃该步

华为机试vs2008测试没问题,,可是提交上去就编译错误,,有人知道原因么?

问题描述 华为机试vs2008测试没问题,,可是提交上去就编译错误,,有人知道原因么? #include #include #define M 1024 int main(){ char str[M]; int length; gets(str); length=strlen(str); for (int i = 1;i<length;i++){ int j=i-1; char temp = str[i]; if(temp<str[j]){ for (j;j >= 0 &&