写点什么

算法题每日一练 --- 第 9 天:第几个幸运数字

作者:知心宝贝
  • 2022 年 7 月 25 日
  • 本文字数:801 字

    阅读完需:约 3 分钟

算法题每日一练---第9天:第几个幸运数字

一、问题描述

到 X 星球旅行的游客都被发给一个整数,作为游客编号。


X 星的国王有个怪癖,他只喜欢数字 3,5 和 7。


国王规定,游客的编号如果只含有因子:3,5,7 就可以获得一份奖品。


我们来看前 10 个幸运数字是:


3 5 7 9 15 21 25 27 35 45


因而第 11 个幸运数字是: 49


小明领到了一个幸运数字 59084709587505,他去领奖的时候,人家要求他准确地说出这是第几个幸运数字,否则领不到奖品。


请你帮小明计算一下,59084709587505 是第几个幸运数字。

二、题目要求

考察

1.for循环,数学思想2.建议用时5~15min
复制代码

运行限制

  • 最大运行时间:1s

  • 最大运行内存: 128M

三、问题分析

首先,编号只能含有 3,5,7 这三个因子的话。一开始我想使用 for 循环,把从 1 到 59084709587505 中间的数字一个个判断。


后来发现不行,一个问题是规模太大没法彻底解决问题,另一个无法计算是否只含有 3,5,7 这三个数字。


后来,我又想到了另一个思路,就是既然你只含有 3,5,7,那我就判断这个数由几个 3,5,7 相乘得到,只要这个数小于目标数字,那么初始定义的 sum=0,计数器 sum++,最后输出结果。


拓展


  • 头文件 #include<math.h>里面的 pow(2,k),可以计算 2 的 k 次方

  • 目标数字太大,超出 int 存储范围,更改为 long longg int 存储

四、编码实现

#include <iostream>#include<math.h>//pow的头文件 using namespace std;int main(){  int i,j,k,sum=0;//初始化   long long int n=59084709587505;//目标数字太大,超出int存储范围,更改为long longg int 存储  for(i=0;pow(3,i)<=n;i++)//第一层3的次方   {    for(j=0;pow(5,j)<=n;j++)//第二层5的次方     {      for(k=0;pow(7,k)<=n;k++)//第三层7的次方       {        if(pow(3,i)*pow(5,j)*pow(7,k)<=n)//所有次方相乘小于目标数字         {          sum++;//sum++        }      }    }  }  cout<<sum-1;//因为0 0 0这种情况不算在内,去除     return 0;}
复制代码

五、输出结果


输出结果为:1905

发布于: 13 小时前阅读数: 28
用户头像

知心宝贝

关注

公众号:穿越计算机的迷雾 2022.03.07 加入

生于尘埃 溺于人海 死于理想高台

评论

发布
暂无评论
算法题每日一练---第9天:第几个幸运数字_算法_知心宝贝_InfoQ写作社区