Project Euler 题解 #40 Champernowne's constant

本文主要是介绍Project Euler 题解 #40 Champernowne's constant，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：Champernowne's constant

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ d₁₀d₁₀₀d₁₀₀₀d₁₀₀₀₀d₁₀₀₀₀₀d_1000000

这个题意是从特定的序列中获取特定的数字，重点在于从序列中分析出特点。

解题思路

1.从数字的位数角度看，有下面的规律：

当数字位数为n位时，所包含的的数字总数为：9

10 ^n-1

n。

例如：n=3,10~99，数字总数为9

2=180。

2.给定D(Z)时，首先需要知道对应的是数字取至一个几位数。便可以知道数字来自哪个数。

通过第1点可以用加法算出来自N位数。

先算出偏移量offset

那么，来自的数字Y = 10 ^n-1+offset/N。

取数字Y中的第几位数呢？

index = N - offset%N。

如何取出数x的第n位数呢？公式如下：

具体应用：

求D(100)。

首先可以知道来自一个2位数，N=2。

offset = 100-9-1 = 90

Y = 10+90/2 = 55

index = 2-90%2 = 2

明显Y的第2位为5。

得D(100) = 5。

代码实现

//https://projecteuler.net/problem=40
//Champernowne's constant
#include <iostream>
#include <cmath>
using namespace std;
int GetNthDigit(unsigned int x, unsigned int N)
{
return N <= 0? 0 : (x/(int)pow(10.0, int(N - 1)))%10;
}
int D(unsigned int x)
{
unsigned int guard = 0;
int N = 0;
do 
{
++N;
guard += 9 * N * (unsigned int)pow(10.0, int(N - 1));
} while (x > guard);
unsigned int offset = x - 1 - (guard - 9 * N * (unsigned int)pow(10.0, int(N - 1)));
unsigned int num = (unsigned int)pow(10.0, int(N - 1)) + offset/N;
unsigned int index = N - offset%N;
return GetNthDigit(num, index);
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<D(1)<<endl;
cout<<D(10)<<endl;
cout<<D(100)<<endl;
cout<<D(1000)<<endl;
cout<<D(10000)<<endl;
cout<<D(100000)<<endl;
cout<<D(1000000)<<endl;
system("pause");
return 0;
}

输入：

D(1) = 1

D(10) = 1

D(100) = 5

D(1000) = 3

D(10000) = 7

D(100000) = 2

D(1000000) = 1
连乘可得210。

这篇关于Project Euler 题解 #40 Champernowne's constant的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！