购物网站后台管理模板,天津做系统集成的公司网站,wordpress本发安装,直通车官网1309#xff1a;【例1.6】回文数(Noip1999)
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 若一个数#xff08;首位不为零#xff09;从左向右读与从右向左读都是一样#xff0c;我们就将其称之为回文数。例如#xff1a;给定一个 10进制数 56#xff0c;将 56加…1309【例1.6】回文数(Noip1999)
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 若一个数首位不为零从左向右读与从右向左读都是一样我们就将其称之为回文数。例如给定一个 10进制数 56将 56加 65即把56从右向左读得到 121是一个回文数。又如对于10进制数87 STEP1 8778 165 STEP2 165561 726 STEP3 7266271353 STEP4135335314884 在这里的一步是指进行了一次N进制的加法上例最少用了4步得到回文数4884。 写一个程序给定一个N2N10或N16进制数 M求最少经过几步可以得到回文数。如果在30步以内包含30步不可能得到回文数则输出“Impossible” 。
【输入】 第1行给定一个N2N≤10或N16表示进制
第2行一个N进制数M。
【输出】 最少几步。如果在30步以内包含30步不可能得到回文数则输出“Impossible”。
【输入样例】 9 87 【输出样例】 6 解析 输入的数据放到数组转换为int 如果值在[0,9]之间则直接-‘0’否则需要-‘A’10 判断是否为回文 将数组和其逆序相加得到新数组**逆序相加数组不需要逆序** 调用判断回文的函数判断新数组 如果不是则重复上述步骤新数组需要归零如果是则直接输出 多个样例调试 【输入】 16 AC27 【输出】 6 【输入】 2 1001101 【输出】 Impossible 【输入】 10 98 【输出】 24
#includebits/stdc.h
using namespace std;
int num0,len_k0 ,m;
int Max200;
int k[200],n0[200],n1[200];//数组只有在全局变量时才会默认为0且数组长度不能为变量
bool plalindrom(int n[],int len){ //回文判断 for(int i0;ilen;i){if(n[i]!n[len-i-1]){return 0;}}return 1;
}
int change(int n1[],int len,int *k){for(int i0;ilen;i){ //倒置相加 放到k k[i]n1[i]n1[len-i-1];}for(int i0;ilen;i){ //转化为m进制 由于是逆序相加所以最后不需要逆序解决进位问题 if(k[i]m){k[i1]k[i]/m;k[i]k[i]%m; }}//处理最后一位 加法最多只会增加一位 int len_newlen;if(k[len_new]mk[len_new]!0){len_new;}return len_new;
}
int main(){char n[Max];int len; cinmn;len strlen(n);for(int i0;ilen;i){ //转化为int if(n[i]0n[i]9){n1[i]n[i]-0; } else{n1[i] n[i]-A10; //当进制n大于10需要考虑字母的情况 } }int mark; //判断是否为回文mark plalindrom(n1,len); len_klen; //先给len_k赋值为len while(!mark(num30)){num;len_kchange(n1,len_k,k); //开始相加 赋值 mark plalindrom(k,len_k); for(int i0;ilen_k;i){ //每一次得到的数组重新倒置后赋给n1以便没有成为回文时继续调用 n1[i]k[i];k[i]0; //由于k数组作为最终加法的值为了保证数值准确每次加后需要归零 }}if(num30) coutnumendl;else coutImpossible;return 0;
}
