首页 > 代码库 > 【编程题目】在从 1 到 n 的正数中 1 出现的次数

【编程题目】在从 1 到 n 的正数中 1 出现的次数

2024-07-18 08:17:32   222人阅读

30.在从 1 到 n 的正数中 1 出现的次数（数组）
题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。
例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1， 10， 1 1 和 12， 1 一共出现了 5 次。

 

思路：
如1121
判断 千位 1出现了多少次：10000 有 0 个 有0个完整的 1000次千位 1， 千位数为1，说明本次千位还没有走完 后面的数字为 121 说明本次千位1走了 122个
判断 百位 1出现了多少次：1000 有 1 个 有1个完整的 100次百位 1， 百位数为1，说明本次百位还没有走完 后面的数字为 21 说明本次百位1走了 22个
判断 十位 1出现了多少次：100 有 11 个 有11个完整的 10次十位 1， 十位数为2，说明本次十位走完了 再加10个1
判断 个位 1出现了多少次：10 有 112 个 有112个完整的 1次十位 1， 个位数为2，说明本次个位走完了 再加1个1
共有 122 + 100 * 1 + 22 + 10 * 11 + 10 + 1 * 112 + 1 个1

#include <stdio.h>#include <math.h>int getNumofOne(int N){    int num = 0; //1出现的次数    int surplus = 0; //对于每一位数字剩余的部分    int times = 1;    for(times = 0; N / int(pow(10.0, times)) != 0; times++)    {        surplus = N % int(pow(10.0, times + 1));        num += (N /int(pow(10.0, times + 1))) * int(pow(10.0, times)); //一定要舍弃小数点后的数字        if ((surplus / int(pow(10.0, times))) > 1)        {            num += int(pow(10.0, times));        }        else if((surplus / int(pow(10.0, times))) == 1)        {            num += surplus % int(pow(10.0, times)) + 1;            }    }    return num;}int main(){    int n = getNumofOne(12);    return 0;}

 

网上看答案，发现大家的思路跟我的都是一样的就是具体的实现过程不大相同。他们有一个共同的特点就是没有用pow函数，值得学习！

http://www.cnblogs.com/GoAhead/archive/2012/05/28/2521415.html 中的实现

#include <stdio.h>int test(int a){    int i;    int num=1;    if(a==0)        return 1;    for(i=1;i<=a;i++)        num*=10;    return num; }int function(int a){    int p=a;    int num=0;    int N=0;    int temp;    int i;    while(p!=0)    {        p=p/10;        N++;    }    p=a;    for(i=1;i<=N;i++){        num+=p/test(i)*test(i-1);        temp=a/test(i-1)%10;        if(temp==1)            num+=a%test(i-1)+1;        if(temp>1)            num+=test(i-1);    }    return num;}void main(){    printf("%d\n",function(88888));}

http://blog.csdn.net/zz198808/article/details/7588335 里的实现

// 1Count.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <windows.h>using namespace std;LONGLONG Sum1s( ULONGLONG n ){    ULONGLONG iCount = 0;    ULONGLONG iFactor = 1;    ULONGLONG iLowerNum = 0;    ULONGLONG iCurrNum = 0;    ULONGLONG iHigherNum = 0;    while( n / iFactor != 0 )    {        iLowerNum = n - ( n / iFactor ) * iFactor;        iCurrNum = (n / iFactor ) % 10;        iHigherNum = n / ( iFactor *10 );        switch( iCurrNum )        {        case 0:            iCount += iHigherNum * iFactor;            break;        case 1:            iCount += iHigherNum * iFactor + iLowerNum + 1;            break;        default:            iCount += ( iHigherNum + 1 ) * iFactor;            break;        }        iFactor *= 10;    }    return iCount;}int main(){    cout << Sum1s(123)<<endl;    system("pause");      return 0;}

 


联系
我们