A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example,
44 32 13 10 1 1
85 89 145 42 20 4 16 37 58 89
Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?
题目大意:
通过将一个数各位的平方不断相加,直到遇到已经出现过的数字,可以形成一个数字链。
例如:
44 32 13 10 1 1
85 89 145 42 20 4 16 37 58 89
因此任何到达1或89的数字链都会陷入无限循环。令人惊奇的是,以任何数字开始,最终都会到达1或89。
以一千万以下的数字n开始,有多少个n会到达89?
算法一:常规方法,从2~10000000逐个判断,同时统计结果
#include<stdio.h> #define N 10000000 int fun(int n) { int t, sum; sum = 0; while(n) { t = n % 10; sum += t * t; n /= 10; } return sum; } void solve(void) { int i, sum, t; sum = 0; for(i = 2; i < N; i++) { t = fun(i); while(1) { if(t == 89) { sum++; break; } else if(t == 1) { break; } else { t = fun(t); } } } printf("%d\n",sum); } int main(void) { solve(); return 0; }
算法二(优化):使用一个bool型数组,保存每次结果,由于最大的中间数为9999999产生的:9^2*7 = 567,所以bool型数组的大小开到600足够
#include <stdio.h> #include <stdbool.h> #define N 10000000 bool a[600] = {false}; int fun(int n) { int t, sum; sum = 0; while(n) { t = n % 10; sum += t * t; n /= 10; } return sum; } void solve(void) { int i, sum, t, temp; sum = 0; for(i = 2; i < N; i++) { t = fun(i); temp = t; if(a[temp]) { sum++; } else { while(1) { t = fun(t); if(a[t] || t == 89) { a[temp] = true; sum++; break; } else if(t == 1) { break; } else { } } } } printf("%d\n",sum); } int main(void) { solve(); return 0; }
Answer:
|
8581146 |
Completed on Sun, 24 Nov 2013, 10:26
相关推荐
今天写的Digit Recognizer属于练习项目,最后的结果只按照测试集的正确率计算排名,没有奖励。解决方案的python代码在Github开源平台上。 Digit Recognizer任务 此任务是在MNIST(一个带Label的数字像素集合)上训练...
is a hard problem. In this paper, we address an equally hard sub-problem in this domain viz. recognizing arbitrary multi-digit numbers from Street View imagery. Traditional approaches to solve this ...
1164:digit函数 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 32194 通过数: 20739 【题目描述】 在程序中定义一函数digit(n,k) ,它能分离出整数n 从右边数第k 个数字。 【输入】 正整数n 和k 。 【输出】 一...
基于python实现的利用kNN实现Digit Recognition,分别从1. 准备数据,对数据进行预处理 2. 选用合适的数据结构存储训练数据和测试元组 3. 设定参数,如k 4.维护一个大小为k的的按距离由大到小的优先级队列,用于存储...
Parallels Desktop 17.1.1 for M1 M1pro (解压码digit77.com).dmg mac电脑M1系列芯片电脑
Digit Recognizer手写数字识别的MINST数据集:包含三个数据文件 sample_submission.csv,test.csv,train.csv
电子时钟字体文件electronicFont DS-DIGIT.TTF
kaggle 竞赛中的手写体数字识别数据集,Digit Recognizes数据集,分为test.csv和train.csv
matlab code for digit recognition
kaggle digit-recoginzer 数字识别数据,用于入门的手写数字识别,常用的deep learning,神经网络,机器学习数据集
matlab开发-NACA4digit。NACA 4位翼型绘图仪。
本指标实现了一个突破系统,它使用了基于 JSatl_Digit 算法处理的最高价和最低价的序列形成的通道。
HTM 算法,On the Optimum Architecture of the Biologically Inspired Hierarchical Temporal Memory Model Applied to the Hand-Written Digit Recognition
指标 ColorJFatl_Digit 在输入参数中有时间帧选项。
一款数码字体,类似于电子手表的字体样式,带HTML使用示例。使用时首先要引入DS-DIGIT.TTF字体文件,在HTMLcss样式添加 font-family:electronicFont;便可生效。 好像不兼容IE浏览器,谷歌使用正常
提供了完整代码。 项目功能要求:可以根据自己手工书写一个数字得带小数,拍照后,程序能将该手写数字转换成对应的数字。 经过查阅资料,将其大致分为一下三个部分: ① 数字的定位、分割、保存. ...
基于 JSatl_Digit_System 指标信号的交易系统。
Tensorflow入门,手写数字图片识别数据集,从https://www.kaggle.com/c/digit-recognizer下载的 包含train.csv,test.csv,sample_submission.csv 从官网下载要注册而且慢=。=