文档章节

一个有关神之数字的小题

薛定谔的兄弟
 薛定谔的兄弟
发布于 2016/03/31 20:15
字数 1441
阅读 11
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

 有这样一个题目:

  • 12 + 92 = 82

  • 82 + 22 = 68

  • 62 + 82 = 100

  • 12 + 02 + 02 = 1

  • 我们看到数字 19 经过上面的过程后结果为1,我们定义所有经历上述过程后结果为1的数字为“神之数字”,毫无疑问,19就是一个神之数字,现在请你设计一个程序,输入一个数字,判断它是否是“神之数字”。

  •       毫无疑问,有一手好代码功夫的人看到如上题目,恐怕都会嗤之以鼻,这算什么?看老夫给你解决它!然而当本小白看了两遍题目后还是一头雾水,这是要干什么?我的老老老老老师祖告诉过我们,要想多快好省地建设程序代码,现在就敲 键盘,但如果想好省多快地建设程序代码,现在应该拿笔在纸上写需求,虽然很啰嗦,我写需求。

  •       给定一个数字,将它的每一位都平方,然后加在一起,直至最后等于1,就是神数。

  •      需求分析完毕,我们设计算法,我们不妨想象一下,我们可以用递归或循环的方法,不断地解离一个数字,然后求平方和,假如平方和等于1,皆大欢喜,它就是神数,然而,如果它一直不等于1呢?我们又怎么判定它下一秒、甚至下一万秒也不会等于1呢?假如不能,岂不是要让它一直循环下去?

  •      这种可怕的情况当然不会出现,因为我们坚信宇宙是简单而又和谐的,不会出现这种情况(好盲目的信仰)。所以我们相信,这其中一定会有相应的数学规律,这也是我今天想说的:

  • 1.万物皆有其规律所在

  •    我们对一个数字进行解离,假如是15,第一次过程后结果为26,第二次过程后结果为40,第三次过程后结果为16,第四次过程后结果为37,第五次过程后结果为58,第六次为89,第七次为145,第八次为42,第九次为20,第十次为4,第十一次为16!

  •     这时,我们发现第十一次的结果与第三次的结果是一样的!假如再进行下去,也不过就是在第三次和第十一次之间徘徊而已,永远不会出现结果1,那么15就不会是神数,因为神数经历最终为1,再经历过程还是为1,我们再度随机抽出几个数进行上述验证,结果皆为如此,这时,我们可以确定,假如一个数在经历过程中出现了重复结果,那它就不是神数,知道了这样的数学规律,我们可以给出如下的代码:

  •    

  • int calcudouble(int n)//一次经历过程函数

  • {

  • int t = 0;

  • int m = 0;

  • do{

  • m = n%10;

  • n = n/10;

  • t = t+m*m; 

  • }while((m != 0) || (n != 0));

  • return t;

  • }

  • int check_godnumber(int n) //判断神数的函数

  • {

  •         int arrayli[10000] = {0};

  • int currentreu = calcudouble(n);

  • arrayli[currentreu] = 1;

  • while(1 != currentreu)

  • {

  • currentreu = calcudouble(currentreu);

  • if(arrayli[currentreu] == 0)

  • {

  • arrayli[currentreu] = 1;

  • }

  • else

  • {

  • break;

  • }

  • }

  • if(currentreu == 1)

  • {

  • return 1;

  •         }

  • else

  • {

  • return 0;

  • }

  •  }

  • 整体的思想是:建立一个数组,数组的所有项全部初始化为0,输入一个数字,一次过程后结果为N,假如N不为1,则数组【N】赋值为1,之后每一次结果都重复如此,在赋值的同时,检查数组【N】是否早就为1,已经为1,表明出现了重复,此数不是神数!

  • 真是皆大欢喜,如果我们只是码农,我们就可以收工了,但是我是要成为码农王的男人!所以,我们还是看看是否有优化的余地吧。。。。

  • 我们发现,申请了一个1000的数组,然而在经历过程中我们只不过使用了其中的某几项,其他的大多数项根本没有用到,这好像有点浪费空间,而我们是不断过程到出现重复过程才能进行判断,这在时间上好像也有浪费,无数码农的经验告诉我们既浪费时间又浪费空间的算法往往不是好的算法,那么,是否还有更好的方法呢?

  • 2.寻找更简单的规律

  • 上次我们测试了15,发现它不是神数,我们继续测试一些数字,发现了另一条规律(有兴趣的可以自己发掘发掘,不再多写过程了):每一个数的过程路径上必定会出现一个小于10的个位数,而我们测试了所有的个位数,假如不是1和7,就会出现重复,也就不是神数!

  • 原来如此,根据这个规律,我给出如下代码:

  • int check_gounumber(int n)

  • {

  • int currentreu = calcudouble(n);

  • while(1 != currentreu)

  • {

  • currentreu = calcudouble(currentreu);

  • if(currentreu < 10)

  • {

  • if(currentreu == 1)

  • {

  • return 1;

  • }

  • else

  • {

  • return 0;

  • }

  • }

  • }

  • return 0;

  • }

  • 相比之前的算法,该算法既节省了空间,又节省了时间,更加地自然而又简洁,让人喜悦。

  • 经过这次做题,我得出新的体会:在解决问题之前,先找准问题相关的规律,能够更加地事半功倍,而找到更好更简单的规律,则是迈向进步的开端。




© 著作权归作者所有

薛定谔的兄弟

薛定谔的兄弟

粉丝 8
博文 20
码字总数 11932
作品 0
丰台
程序员
私信 提问
以思无意,不如发帖。(PS: 关于算法,有难度。)

在网上看到这样一个题,想了很久,始终没有思路。题目是这样的,请看: 仔细观察下面的数字组成的三角形: 3 1 4 5 6 2 看出什么特征吗? 首先,它包含了1~6的连续整数。 重要的是:每个数字...

空云万里晴
2013/04/08
540
3
leetcode算法题解(Java版)-6-链表,字符串

一、字符串处理 题目描述 Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. 思路 把数字转化为罗马符号,根据罗马符号的规律...

kissjz
2018/05/03
0
0
java如何编写数字金字塔

java当中,如何实现打印出一个数字金字塔?如下图所示 这是正的数字金字塔,还有倒立的数字金字塔 我在开源中国社区搜索了一下,总共有4篇搜索结果,但是感觉作用都不大,所以发问求解答。 ...

水晶之夜
2014/01/16
7.5K
9
采购单(京东2017秋招真题)

本来也不算很难的一道题,但是总是只通过60% 或者 80% 一眼就看出思路,代码也不难的题就是不能全部通过也是神烦,应该是格式上的问题,也不算完全弄明白了,简单说说,作为一种经验。 思路:...

256785haha
2018/06/26
0
0
【算法】LeetCode算法题-Roman To Integer

这是悦乐书的第145次更新,第147篇原创 今天这道题和罗马数字有关,罗马数字也是可以表示整数的,如“I”表示数字1,“IV”表示数字4,下面这道题目就和罗马数字有关,你能猜到吗? 01 看题和...

小川94
2018/10/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么面试必问线程状态?你的回答满分了吗

看很多同学的面经、网上的面试资料,都不约而同的提到了一个基础问题:“你知道线程有几种状态吗?状态之间的扭转是怎样的?”,有准备的同学都知道有五种:New(新建)、Runnable(可运行)...

Z_J_H
28分钟前
4
0
如何保障云上数据安全?一文详解云原生全链路加密

点击下载《不一样的 双11 技术:阿里巴巴经济体云原生实践》 本文节选自《不一样的 双11 技术:阿里巴巴经济体云原生实践》一书,点击上方图片即可下载! 作者 李鹏(壮怀)阿里云容器服务高...

阿里巴巴云原生
28分钟前
3
0
获取数组的第一个元素

我有一个数组: array( 4 => 'apple', 7 => 'orange', 13 => 'plum' ) 我想获得此数组的第一个元素。 apple 预期结果: apple 一个要求: 它不能通过引用传递来完成 ,所以array_shift不是一......

javail
30分钟前
4
0
哈希情史知多少

<p align="right">——日拱一卒,不期而至!</p> 简介 hash是我们工作中经常听到的词,比如哈希表、哈希函数、hashCode、HashTable、HashMap等等,那么它们之间到底有怎样的爱恨情仇呢?来一...

彤哥读源码
37分钟前
4
0
SpringCloud 学习(5) --- Zuul(一)基本概念、配置

[TOC] Spring Cloud eureka:注册中心 服务端:提供注册 客户端:进行注册 ribbon:负载均衡(集群) Hystrix:熔断器,执行备选方案 Feign:远程调用 Zuul:网关,统一入口。 1.1、一夫当关,...

庭前云落
39分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部