wordpress动漫整站,大型网站制作公司,电子商务网站推广案例,网络营销专业大学排名文章目录 好数题目描述暴力方法一暴力方法二#xff08;超时#xff09; 好数
题目描述
【问题描述】 一个整数如果按从低位到高位的顺序#xff0c;奇数位#xff08;个位、百位、万位 #xff09;上的数字是奇数#xff0c;偶数位#xff08;十位、千位、十万位 … 文章目录 好数题目描述暴力方法一暴力方法二超时 好数
题目描述
【问题描述】 一个整数如果按从低位到高位的顺序奇数位个位、百位、万位 · · · 上的数字是奇数偶数位十位、千位、十万位 · · · 上的数字是偶数我们就称之为“好数”。
给定一个正整数 N请计算从 1 到 N 一共有多少个好数。 【输入格式】 一个整数 N。 【输出格式】 一个整数代表答案。 【样例输入 1】
24【样例输出 1】
7【样例输入 2】
2024【样例输出 2】
150【样例说明】 对于第一个样例24 以内的好数有 1、3、5、7、9、21、23一共 7 个。
【评测用例规模与约定】 对于 10% 的评测用例1 ≤ N ≤ 100。 对于 100% 的评测用例1 ≤ N ≤ 107。
暴力方法一
从题目中可以得出结论奇数位个位、百位、万位 · · · 上的数字是奇数偶数位十位、千位、十万位 · · · 上的数字是偶数
那么就可以定义一个k代表数字n的当前位数从1开始计数即个位是1十位是2百位是3……
然后就可以从个位开始取数判断该数是否为好数每取走一位k加上1进入下一位
// 包含C程序中常用的库是C标准库的一个集合包括了I/O、字符串和容器等
#includebits/stdc.h
// 使用std命名空间中的名字避免每次调用标准库中的东西都要加上std::前缀
using namespace std;// 定义一个函数check用于检查某个整数n是否是“好数”
bool check(int n)
{int k1; // 代表数字n的当前位数从1开始计数即个位是1十位是2百位是3以此类推// 循环检查整数n的每一位while(n){int tn%10; // t为n的当前最低位的数字%运算符取余数// 检查当前位数k是否与对应的数字t符合好数的定义if(k%21 t%20) // 如果位数k是奇数但数字t是偶数则不满足好数的定义return false; // 返回false表示n不是好数if(k%20 t%21) // 如果位数k是偶数但数字t是奇数则不满足好数的定义return false; // 返回false表示n不是好数n / 10; // n去掉最低位的数字/运算符用来对n除以10并将结果赋值给nk; // 增加位数计数器因为已经检查了一位}// 如果所有位的检查都通过则n是好数return true; // 返回true表示n是好数
}// 程序的主函数
int main()
{int n; // 定义一个整型变量n用来存放输入的数字cin n; // 从标准输入流中读取一个整数到变量nint ans 0; // 初始化答案变量ans用于计数有多少个好数// 循环从1开始到n结束for(int i1; in; i){// 调用check函数检查i是否是好数if(check(i))ans; // 如果i是好数就将答案变量加1}// 输出答案cout ans;// 返回0标识程序正常结束return 0;
}暴力方法二超时
分情况讨论
当该数位数为奇数时可以得到结论偶数位上是奇数奇数位上是偶数当该数位数为偶数时可以得到结论偶数位上是偶数奇数位上是奇数
代码如下
// 包含C标准库的头文件用于I/O操作和字符串处理
#includebits/stdc.h
using namespace std;int main() {int n; // 定义一个整数变量n用来存储输入的整数Ncin n; // 从标准输入流中读取一个整数到n中int ans 0; // 定义并初始化计数器ans用来记录总的好数的数量// 用一个for循环遍历从1到n的所有整数检查每个数是否为好数for(int i 1; i n; i) {string s; // 定义一个字符串s用来存储当前数字的字符串表示s to_string(i); // 把当前的整数i转化为字符串格式存储在s中int flag 0; // 定义一个标识变量flag用来表示当前数是否为好数// 当数字的位数为奇数时进行检查if(s.size() % 2 1) {// 遍历数字的每一位for(int j 0; j s.size(); j) {// 如果位数是奇数位从0开始计数但数字是偶数设置标志并跳出循环if(j % 2 0 (s[j] - 0) % 2 0) {flag 1;break;}// 如果位数是偶数位但数字是奇数设置标志并跳出循环if(j % 2 1 (s[j] - 0) % 2 1) {flag 1;break;}}}// 如果数字的位数为偶数进行检查if(s.size() % 2 0) {// 同样地遍历数字的每一位for(int j 0; j s.size(); j) {// 如果位数是奇数位但数字是偶数设置标志并跳出循环if(j % 2 0 (s[j] - 0) % 2 1) {flag 1;break;}// 如果位数是偶数位但数字是奇数设置标志并跳出循环if(j % 2 1 (s[j] - 0) % 2 0) {flag 1;break;}}}// 如果flag没有被设置说明当前的数是一个“好数”if(flag 0)ans; // 好数的数量加1}cout ans; // 输出总的好数的数量return 0; // 程序结束
}这段代码通过将数字转换成字符串的形式然后检查字符串的每个字符来判断一个数是否符合“好数”的定义。代码中的flag变量用来表示当前检查的数是否已经确定不是“好数”。如果在检查过程中发现某位数字不符合好数的要求flag将被设置为1并终止进一步检查。最终没有被标记为非好数的数将会被计入最终的答案ans中。
