首页 > 试题广场 >

幸运数

[编程题]幸运数

热度指数：23990 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小明同学学习了不同的进制之后，拿起了一些数字做起了游戏。小明同学知道，在日常生活中我们最常用的是十进制数，而在计算机中，二进制数也很常用。现在对于一个数字x，小明同学定义出了两个函数 f(x) 和 g(x) 。 f(x) 表示把x这个数用十进制写出后各个数位上的数字之和。如f(123)=1+2+3=6 。 g(x) 表示把x这个数用二进制写出后各个数位上的数字之和。如 123 的二进制表示为 1111011 ，那么，g(123)=1+1+1+1+0+1+1=6 。小明同学发现对于一些正整数 x 满足 f(x)=g(x) ，他把这种数称为幸运数，现在他想知道，大于0且小于等于n的幸运数有多少个？

数据范围： $1 \le n \le 10^5 \$

输入描述:

每组数据输入一个数

输出描述:

每组数据输出一行，小于等于n的幸运数个数。

示例1

输入

输出

算法知识视频讲解

琅琊榜第一BUG

```
#!/usr/bin/env python 
# -*- coding:utf-8 -*-  
__author__ = 'liuhui'  

import sys 
class Solution: 
    def luckyNum(self, n):
        number = 0  
        for i in range(1, n+1):
            strn = str(i)
            fn = 0  
            for j in range(len(strn)):
                fn += int(strn[j])
            xn = 0  
            while i >= 2:
                a = i % 2  
                i //= 2  
                xn += a
            xn += i 
            if xn == fn:
                number += 1  
        return number 
if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    solut = Solution()
    res = solut.luckyNum(n) print(res)

```

发表于 2017-08-22 13:40:50 回复(0)

更多回答

dragonhaw

package 幸运数;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			int count = 0;
			for (int i = 1; i <= n; i++) {
				if (f(i) == g(i)) {
					count++;
				}
			}
			System.out.println(count);
		}
	}
	/** 二进制 */
	private static int g(int n) {
		int sum = 0;
		while (n != 0) {
			sum += n % 2;
			n /= 2;
		}
		return sum;
	}
	/** 十进制 */
	private static int f(int n) {
		int sum = 0;
		while (n != 0) {
			sum += n % 10;
			n /= 10;
		}
		return sum;
	}
}

发表于 2017-08-16 12:16:17 回复(0)

324134134143428

数据是从1开始的而不是从0开始的其余的就没有什么了

点赞交友，点赞之交

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<stdlib.h>
#define N 30;
using namespace std;
int f(int i)
{
	int sum = 0;
	while(i)
	{
		sum+=i%10;
		i/=10;
	}
	return sum;
}
int g(int i)
{
	int sum = 0;
	for(int j = 1;j<100000;j*=2)
	{
		if((j&i)==j) sum++;
	}
	return sum;
}
int main()
{
	//cout<<f(123)<<endl;cout<<g(123)<<endl;
	int n;
	while(cin>>n)
	{
		int sum = 0;
		for(int i = 1;i<=n;i++)
		{
			if(f(i)==g(i)) {sum++;}
		}
		cout<<sum<<endl;
	}
    return 0;
}

编辑于 2017-08-20 16:12:31 回复(2)

Python

华科平凡

一行

print(sum([sum(map(int, list(bin(i).replace("0b", ""))))==sum(map(int, list(str(i)))) for i in range(1, int(input()) + 1)]))

等价于：

res = 0
for i in range(1, int(input()) + 1):
    binVal = sum(map(int, list(bin(i).replace("0b", ""))))
    decimalVal = sum(map(int, list(str(i))))
    if decimalVal == binVal:
        res += 1
print(res)

编辑于 2018-11-23 06:53:48 回复(4)

Java

哎呦呦呦呦丁

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
        int count=0;
        for(int i=1;i<=n;i++){
            if(f(i)==g(i))
                count++;
        }
        System.out.println(count);
    }
    public static int f(int n){
        int sum=0;
        while(n!=0){
            sum+=n%10;
            n=n/10;
        }
        return sum;
    }
    //把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0，
    //那么一个整数的二进制表示有多少个1，就可以进行多少次这样的操作

    public static int g(int n){
        int sum=0;
        while(n!=0){
            n=n&(n-1);
            sum++;
        }
        return sum;
}
}

发表于 2017-10-19 20:07:36 回复(0)

Holiday_12138


	//2 3题真的不是一样的吗。。



	importjava.util.Scanner;



	 



	publicclassMain {



	    publicstaticvoidmain(String[] args) {



	        Scanner sc = newScanner(System.in);



	        intn;



	        while(sc.hasNext()) {



	            n = sc.nextInt();



	            intcount = 0;



	            for(inti = 1; i <= n; i++) {



	                intcount1 = convert(i, 10);



	                intcount2 = convert(i, 2);



	                if(count1 == count2) {



	                    count++;



	                }



	            }



	            System.out.println(count); 



	        }



	    }



	     



	    publicstaticintconvert(inta, intw) {



	        intcount = 0;



	        while(a > 0) {



	            count += a%w;



	            a /= w;



	        }



	        returncount;



	    }



	     



	}

发表于 2017-07-12 11:40:09 回复(0)

GYshadows

暴力解法：围观一波
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        int [] sta = {1,20,21,122,123,202,203,222,223,230,231,302,303,410,411,502,503,1130,1131,1150,1151,1202,1203,1212,1213,1230,1231,1300,1301,1402,1403,1502,1503,1510,1511,2006,2007,2032,2033,2102,2103,2200,2201,3006,3007,3012,3013,3050,3051,3070,3071,3102,3103,3110,3111,3300,3301,4014,4015,5000,5001,5010,5011,5020,5021,6002,6003,6012,6013,6102,6103,7000,7001,7102,7103,8110,8111,10006,10007,10032,10033,10050,10051,10060,10061,10070,10071,10112,10113,10132,10133,10170,10171,10234,10235,10310,10311,10410,10411,10430,10431,11012,11013,11050,11051,11070,11071,11114,11115,11134,11135,11150,11151,11214,11215,11240,11241,11250,11251,11260,11261,11300,11301,11502,11503,11710,11711,12006,12007,12024,12025,12112,12113,12142,12143,12204,12205,12214,12215,12250,12251,13012,13013,13050,13051,13200,13201,13230,13231,14014,14015,14020,14021,14102,14103,14330,14331,15002,15003,15010,15011,15020,15021,15030,15031,15210,15211,15230,15231,15310,15311,16010,16011,16030,16031,16102,16103,16120,16121,16300,16301,16310,16311,20004,20005,20040,20041,20050,20051,20060,20061,20112,20113,20142,20143,20206,20207,20230,20231,20312,20313,20320,20321,20340,20341,20414,20415,20420,20421,21002,21003,21022,21023,21030,21031,21112,21113,21202,21203,21212,21213,21220,21221,21302,21303,21400,21401,22006,22007,22030,22031,22120,22121,22130,22131,22140,22141,22210,22211,22220,22221,22230,22231,22302,22303,22310,22311,22500,22501,23004,23005,23012,23013,23110,23111,23210,23211,23230,23231,24002,24003,24012,24013,24022,24023,24100,24101,24302,24303,24510,24511,26100,26101,30006,30007,30042,30043,30050,30051,30060,30061,30070,30071,30104,30105,30112,30113,30132,30133,30150,30151,30210,30211,30220,30221,30230,30231,30320,30321,30400,30401,30420,30421,30500,30501,30702,30703,31004,31005,31012,31013,31120,31121,31150,31151,31214,31215,31300,31301,31400,31401,31410,31411,31420,31421,31610,31611,31710,31711,32002,32003,32012,32013,32022,32023,32112,32113,32212,32213,32250,32251,32302,32303,32410,32411,32502,32503,32700,32701,40002,40003,40012,40013,40022,40023,40122,40123,40200,40201,40210,40211,40220,40221,40400,40401,40430,40431,40510,40511,40700,40701,41210,41211,42100,42101,43004,43005,44000,44001,44020,44021,45000,45001,45010,45011,45020,45021,47100,47101,50002,50003,50012,50013,50020,50021,50300,50301,51010,51011,51020,51021,51030,51031,51130,51131,52010,52011,52030,52031,52110,52111,52200,52201,52210,52211,52220,52221,53102,53103,53210,53211,54010,54011,60002,60003,60012,60013,60022,60023,60102,60103,60120,60121,60200,60201,60210,60211,60220,60221,60300,60301,60310,60311,60400,60401,61002,61003,61022,61023,61030,61031,61210,61211,61302,61303,61400,61401,62010,62011,62110,62111,62200,62201,63102,63103,65000,65001,65010,65011,65020,65021,70010,70011,70110,70111,71100,71101,80110,80111,90000,90001,90030,90031};
        int result = 0;
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        for(int num: sta){
            if(num <= n)
                result++;
        }
        System.out.print(result);
    }
}

发表于 2018-08-27 21:08:18 回复(0)

Python

yzdeng

def decimal(n):
    x=[int(x) for x in str(n)]
    s=sum(x)
    return s
def binary(n):
    x=[x for x in str(bin(n))]
    x=x[2:]
    y=[int(x) for x in x]
    s=sum(y)
    return s

n=int(input())
count=0
for i in range(1,n+1):
    if decimal(i)==binary(i):
        count+=1
print(count)

发表于 2018-05-22 21:36:40 回复(0)

千手寂洛

#include<iostream>
using namespace std;

int f(int x){
    int fx=0;
    while(x>0){
        fx+=x%10;
        x/=10;
    }
    return fx;
}
int g(int x){
    int gx=0;
    while(x>0){
        gx+=x&1;
        x>>=1;
    }
    return gx;
}
int main(){
    int n;
    cin>>n;
    int count=0;
    for(int i=1;i<=n;i++){
        if(f(i)==g(i))
            count++;
    }
    cout<<count<<endl;
    return 0;
}

发表于 2019-04-10 22:08:25 回复(0)

Java

不知道·就是喜欢

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int countsum=0; //存储幸运数个数
        for (int i = 1; i <=num; i++) {
            int count=0;
            for (int j = 0; j < 32; j++) {
                if(((i >> j) & 1) == 1){ //判断有多少个1，并相加，和为 count，是 g(x)
                    count++;
                }
            }
            String s = i+"";
            char[] arr = s.toCharArray();
            int sum = 0; //sum是各位相加的和，是f(x)
            for (char c : arr) {
                sum = sum + (c-48); //48是 0 的ASCII码值也可以用 '0' 代替
            }
            if(sum == count){ //判断f(x)是否等于g(x)
                //System.out.println(i);
                countsum++;
            }
        }
        System.out.println(countsum);
    }
}

发表于 2018-07-26 09:38:27 回复(0)

黄小斜

还行
import java.util.Scanner;

public class Main{
     public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(lucky(n));
    }
    public static int lucky(int n) {
        int cnt = 0;
        for (int i = 1 ;i <= n;i ++) {
            String s = String.valueOf(i);
            int sum = 0;
            for (int j = 0;j < s.length();j ++) {
                sum += Integer.parseInt(s.substring(j,j + 1));
            }
            int bitcnt = Integer.bitCount(i);
            if (sum == bitcnt) {
                cnt ++;
            }
        }
        return cnt;
    }
}

发表于 2018-06-06 22:21:51 回复(0)

tp_16b

 #include <iostream>
 #include <string>
 #include <cstdlib>
 #include <cstdio>
 using namespace std;
 int get_sum_10( int n)
 {
     int sum = 0;
     while( n != 0)
     {   
         sum+= n%10;
         n/= 10;
     }
     return sum;
 }
 int get_sum_2( int n)
 {
     int count = 0;
     while(n)
     {
         if( (n&0x1) == 1)
             ++count;
         n>>= 1;
     }
     return count;
 }
 int GetLuckNum( int n)
 {
     int result = 0;
     if( n<= 100000)
     {
         int count = 0;
         for( int i = 1; i<= n; ++i)
         {
             if( get_sum_10(i) == get_sum_2(i))
                 ++count;
         }
         result = count;
     }
     return result;
 }
 int main( )
 {
     int n;
     while( cin>>n)
         cout<<GetLuckNum( n)<<endl;
 }

编辑于 2018-06-04 23:29:49 回复(0)

C/C++

❤波雅汉库克❤

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int f(int x)
{
int s=0;
while(x>0)
{
s+=x%10;
x/=10;
}
return s;
}
int g(int x)
{
int s=0;
while(x)
{
x=x&(x-1);
s++;
}
return s;
}
int main()
{
int n;
int index=0;
cin>>n;
for(int i=1;i<=n;i++)
if(f(i)==g(i))
index++;
cout<<index<<endl;
return 0;
}

发表于 2018-05-16 19:38:51 回复(0)

一匹努力的千里马

100% ac

思路：分治的思想。

import java.util.Scanner;


public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = 0;
        int n = sc.nextInt();
        for(int i = 1; i <= n;i++) {
            int fres = fFunction(i);
            int gres = gFunction(i);
            if(fres == gres) count++;
            
        }
        System.out.println(count);
    }
    
    private static int fFunction(int i) {
        int tmp = i;
        int count = 0;
        while(tmp != 0) {
            count += tmp%10;
            tmp/= 10;
        }
        return count;
    }
    private static int gFunction(int i) {
        int tmp = i;
        int count = 0;
        while(tmp != 0) {
            count += tmp%2;
            tmp/= 2;
        }
        return count;
    }
}

发表于 2018-05-10 15:11:48 回复(0)

北理工恶龙

#include<iostream>

using namespace std;

int f(int n){
    int sum_f = 0;
    while(n){
        sum_f += n % 10;
        n /= 10;
    }
    return sum_f;
}

int g(int n){
    int sum_g = 0;
    while(n){
        sum_g += n % 2;
        n /= 2;
    }
    return sum_g;
}

int main(){
    int n,count = 0;
    cin >> n;
    for(int i = 1;i <= n;i++){
        if(f(i) == g(i))
            count++;
    }
    cout << count << endl;
    return 0;
}

编辑于 2018-04-08 19:15:07 回复(0)

兜一圈就回去

##中心思想就是取余数相加
def fg(x,i):

    s = 0
    while (x >= 1):
        s += x % i
        x = int(x/i)
    return s

n = int(input())
num = 0
for i in range(1,n+1):
    if fg(i,10) == fg(i,2):
        num += 1
print (num)

发表于 2018-04-04 14:21:31 回复(0)

RhythmLian

#看了一下没有python的解法，过来水一发：利用python的bin可以把整数转为二进制。
def f(s):
    ans=0
    for i in s:
        ans+=int(i)
    return ans
def g(s):
    ans=0
    for i in s:
        if i=='1':
            ans+=1
    return ans
res=0
for i in range(1,int(input())+1):
    if g(str(bin(i)))==f(str(i)):
        res+=1
print(res)

发表于 2018-01-24 10:15:16 回复(1)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int Fun(int n, int m)
{     int sum = 0;     while(n)     {         sum += n%m;         n /= m;     }     return sum;
}

int main()
{     int n;     while(cin>>n)     {         int count = 0;         for(int i=1;i<=n;i++)         {             if(Fun(i,10) == Fun(i,2))                 count++;         }         cout<<count<<endl;     }     return 0;
}

发表于 2017-12-31 02:13:22 回复(0)

graper

//应用转化为二进制后进行计算，加上sstream来进行实现

#include <iostream>

#include <bitset>
#include <sstream>
#include "string.h"
using namespace std;

int f(long x)
{
    long sum = 0;
    while (x>=10)
    {
        sum += x % 10;
        //cout << sum << "sum";
        x = x / 10;
    }
    return sum += x;
}
int g(char m[])
{
    int len = strlen(m);
    int sum = 0;
    for (int i = 0; i < len; i++)
    {
        sum =sum+m[i]-48;
        //cout << m[i]<<" ";
    }
    //cout <<"sum"<< sum << endl;
    return sum;
}
int main()
{
    long n;
    char m[100];
    long sum = 0;
    cin >> n;


    while (n)
    {
        stringstream ss;
        bitset<32> nb;
        nb = n;
        ss << nb;
        ss >> m;
        //cout << g(m) <<" "<< f(n) << endl;
        if (f(n) == g(m))
            sum += 1;
        n--;
    }
    cout << sum << endl;
    return 0;
}

发表于 2017-11-20 16:49:06 回复(0)

啊咿呀嘿

<?php

$num = fgets(STDIN);


function sumEvery($num){
        $num=strval($num);
        $sum = 0;
        for($i=0; $i<strlen($num); $i++){

                $sum += $num[$i];
        }
        return $sum;
}

$count = 0;
for($j=1; $j<=$num; $j++){
        //var_dump($j.'='.sumEvery($j).'---'.'decbin($j)='.sumEvery(decbin($j)));
        if(sumEvery($j) == sumEvery(decbin($j))){
                $count++;
        }
}

echo $count;

发表于 2017-09-14 21:33:01 回复(0)

安大爷写代码


	#include <iostream> 



	using namespace std; 



	int getSum(int x,int bit) 



	{ 



	    int sum = 0; 



	    while(x>0) 



	    { 



	        sum += x % bit; 



	        x /= bit; 



	    } 



	    return sum; 



	} 



	int main() 



	{ 



	    int x,i,sum = 0; 



	    cin>>x; 



	    for(i=0;i<=x;i++) 



	    { 



	        if(getSum(i,10)==getSum(i,2)) 



	            sum++; 



	    } 



	    cout<<sum<<endl; 



	    return 0; 



	}