`

(Problem 92)Square digit chains

阅读更多

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 recognizor.rar

    今天写的Digit Recognizer属于练习项目,最后的结果只按照测试集的正确率计算排名,没有奖励。解决方案的python代码在Github开源平台上。 Digit Recognizer任务 此任务是在MNIST(一个带Label的数字像素集合)上训练...

    Multi-digit Number Recognition from Street View Imagery using DCNN

    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函数.cpp

    1164:digit函数 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 32194 通过数: 20739 【题目描述】 在程序中定义一函数digit(n,k) ,它能分离出整数n 从右边数第k 个数字。 【输入】 正整数n 和k 。 【输出】 一...

    利用kNN实现Digit Recognition

    基于python实现的利用kNN实现Digit Recognition,分别从1. 准备数据,对数据进行预处理 2. 选用合适的数据结构存储训练数据和测试元组 3. 设定参数,如k 4.维护一个大小为k的的按距离由大到小的优先级队列,用于存储...

    JSatl_Digit_System - MetaTrader 5脚本.zip

    《JSatl_Digit_System - MetaTrader 5脚本解析》 在金融交易领域,MetaTrader 5(MT5)是一款广泛使用的交易平台,它为交易者提供了丰富的技术分析工具和自动化交易策略。本篇将深入探讨名为"JSatl_Digit_System"的...

    电子时钟字体文件electronicFont DS-DIGIT.TTF

    电子时钟字体文件,如"electronicFont DS-DIGIT.TTF",是计算机系统中用于显示具有电子感或数字风格的字体类型。这种字体通常用于模拟数字显示器的效果,常见于各种界面设计、数字艺术、电子设备显示以及时钟应用...

    digit recognizor.zip

    机器学习,特征选择所用到的数据。泰坦尼克

    digit-recongizer.zip

    《手写数字识别:kaggle digit-recoginzer数据集深度解析》 在数字化的世界里,自动识别手写数字是一项极具挑战性的任务,广泛应用于邮政编码、支票验证、智能交互界面等领域。kaggle的`digit-recoginzer`项目提供...

    digit-recognizer.zip

    标题中的"digit-recognizer.zip"表明这是一个与数字识别相关的数据集,通常用于训练和测试机器学习模型。这种数据集通常包含手写数字图像,是机器学习领域经典的MNIST(Modified National Institute of Standards ...

    Parallels Desktop 17.1.1 for M1 M1pro (解压码digit77.com).dmg

    Parallels Desktop 17.1.1 for M1 M1pro (解压码digit77.com).dmg mac电脑M1系列芯片电脑

    Exp_XHullTrend_Digit - MetaTrader 5EA.zip

    《MetaTrader 5 EA——Exp_XHullTrend_Digit深度解析》 在交易领域,自动交易系统(Expert Advisor,简称EA)已经成为许多交易者的重要工具。本文将深入探讨一个名为"Exp_XHullTrend_Digit"的MetaTrader 5(MT5)EA...

    Exp_JSatl_Digit_System - MetaTrader 5EA.zip

    《JSatl_Digit_System - MetaTrader 5 EA的深度解析》 在金融交易领域,自动交易系统(Expert Advisor,简称EA)已经成为许多交易者的重要工具。本文将详细探讨一款名为"Exp_JSatl_Digit_System"的MetaTrader 5 EA...

    codes.rar_digit_digit recognition

    标题中的"codes.rar_digit_digit recognition"表明这是一个关于数字识别的MATLAB代码压缩包。描述中提到的"matlab code for digit recognition"进一步确认了这个项目是利用MATLAB编程语言进行数字识别的技术实现。 ...

    matlab开发-NACA4digit

    NACA4digit是NACA翼型系列中的一种,它通过一个四位数字代码来描述翼型的几何特性。这个代码包含了翼型厚度分布、最大厚度位置以及曲率等关键信息。MATLAB作为一种强大的计算和图形化工具,被广泛用于此类翼型的设计...

    Kaggle Digit Recognize数据集

    《Kaggle Digit Recognize数据集:深度学习与图像识别的探索》 在信息技术领域,机器学习和深度学习已经成为主流的研究方向,而图像识别作为其中的重要应用,已经深入到我们生活的方方面面。Kaggle作为全球知名的...

    Digit-Recognizer-master.zip

    《基于PyTorch的手写数字识别:Kaggle上的Digit Recognizer项目解析》 在机器学习领域,图像识别是一项基础且重要的任务,特别是在手写数字识别方面,它有着广泛的应用,如银行支票识别、邮政编码自动处理等。...

    像素数字js插件digitNumber.js

    **像素数字js插件digitNumber.js**是一种专为Web前端设计的数字显示插件,它提供了丰富的数字表现形式,如像素数字、百分比、记分薄以及电子时钟的实现。该插件的核心特性在于其动画效果,支持渐变和滚动增加两种...

Global site tag (gtag.js) - Google Analytics