下面这段代码输出结果是什么？
a = 1 b = -2 c = a / b print c print int(c) print int(-0.5)
输出结果为：-1, -1, 0
如果是在C++中
int a = 1; int b = -2; int c = a/b; cout<<c<<endl; //输出 0
这说明一个正整数和一个负整数相除，结果不是期望的结果（-1，而不是期望的0），即在强制转换过程中没有得到预期的强制转换结果。
a = 1 b = -2 c = a * 1.0 / b # 注意：将一个操作数*1.0，转化为浮点运算 print c # -0.5 print int(c) # 0 print int(-0.5)# 0
注意：必须是将a/b的一个操作数转换为浮点型（通过*1.0，如(a*1.0) /b），对a/b的整体结果转换为浮点数（即a/b *1.0 ）仍然是不对的。
下述代码中声明类Example对象的数组e[2]，然后新建了Example(1)对象并赋值给e[0]。通过这种方式设置类对象数组，称为赋值，而不是初始化。这个过程实际上赋值过程，存在临时对象Example(1)的构造和析构。而通过类对象数组初始化就不存在生成临时对象这一过程。先看类对象数组声明和赋值的代码：
class Example
{
public:
Example():id(0){cout<<"Example():0"<<endl;} //无参构造构造
Example(int id):id(id){cout<<"Example():"<<id<<endl;} //有参构造函数
~Example(){cout<<"~Example():"<<id<<endl;}
private:
int id;
};
int main()
{
Example e[2]; //调用默认的无参构造函数，如果不存在无参构造函数，则会编译报错。
// 调用有参构造函数使用初始化方式 Example e[2] = {Example(1),Example(2)};
e[0] = Example(1); //新建临时对象Example(1)，调用copy assignment operator操作符拷贝给e[0]对象。
// Example(1)对象的生成周期只在该语句，语句结束后就会调用析构函数释放。
return 0;
}
函数的输出为
Example():0 Example():0 Example():1 ~Example():1 ~Example():0 ~Example():1
首先，调用无参构造函数，生成两个Example对象，所以输出两个Example():0
然后，执行Example(1) 调用有参构造函数，生成一个临时的Example类对象，所以输出Example():1。然后将临时对象拷贝赋值给e[0]。该条赋值语句结束后，临时对象的生成周期就过了，调用析构函数释放内存，所以输出~Example():1。此时e[0]的id也变成了1。
最后程序结束，数组e要释放，调用e[0]和e[1]的析构函数释放内存。关于为什么先释放e[1]后释放e[0]后面会有说明。
Example e[2] = {Example(1),Example(2)};
这种方式直接初始化了数组元素为Example(1) 和 Example(2)，只分别调用了一次Example(1) 和 Example(2)的构造函数，并赋值给了数组。整个过程没有生成临时对象。
class Example
{
public:
Example():id(count){count++;} //每构造一个对象，计数值++
void print(){cout<<id<<endl;} //输出当前对象的id
~Example(){cout<<"~Example():"<<id<<endl;}
private:
int id; //类对象的id
static int count; //类对象计数。为Example类所有。
};
int Example::count = 0;
int main()
{
Example e[3];
e[0].print();
e[1].print();
e[2].print();
return 0;
}
程序输出为
0 1 2 ~Example():2 ~Example():1 ~Example():0
由上可知，类数组的构造过程是自底向上的，析构过程是自顶向下的。如下图所示：
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
质数的排列。
Python的实现思路：可以现将所有的4位数的质数保存到primes中，然后将所有含有4个相同数字的质数分成一组，并将所有组保存到groups中。遍历groups，找出满足条件：(1) 小组中至少含有三个元素，(2) 小组中存在三个元素形成等差。
C++实现思路详见C\C++方法1
方法1 [感谢aitormoreno 给出的伪代码，思路十分清晰] 保存所有质数在primes中，遍历primes判断两个质数是否含有相同数字，是则找等差的第三项，判断第三项是否在primes中，且含有相同的数字，是则符合条件，输出结果。 伪代码如下
for (int i=0; i<NUMPRIMES; i++){ //遍历所有质数
for(int j=i+1; j<NUMPRIMES; j++){
if (sameDigits(primes[i], primes[j])){ //判断两个质数是否含有相同的数字
int diff = primes[j]-primes[i];
int last = primes[j]+dif; //等差数列第三个数
if (find_prime(last) && samedigits(lastP, primes[i])){ //判断等差的第三个数是否在primes中且含有相同的数字
printf("%d %d %d\n", primes[i], primes[j], lastP); //符合条件，输出结果
}
}
}
}
完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/************************************************************************
* 判断n是否是质数
************************************************************************/
bool is_prime(int n)
{
if (n <= 1)
{
return false;
}
else if (n == 2 || n == 3)
{
return true;
}
else if (n % 2 == 0)
{
return false;
}
else
{
for (int i=3;i<=(int)sqrt((float)n);i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
}
/************************************************************************
* 判断a和b是否含有相同的数字
************************************************************************/
bool same_digits(int a,int b)
{
vector<int> va(4);
vector<int> vb(4);
while(a != 0 && b != 0)
{
va.push_back(a%10);
vb.push_back(b%10);
a /= 10;
b /= 10;
}
sort(va.begin(),va.end());
sort(vb.begin(),vb.end());
return va == vb;
}
int main()
{
vector<int> primes; //保存所有四位数的质数
for (int n=1000;n<=9999;n++)
{
if(is_prime(n)) primes.push_back(n);
}
int NUMPRIMES = primes.size(); //质数个数
for (int i=0;i<NUMPRIMES-2;i++) //遍历所有质数
{
for (int j=i+1;j<NUMPRIMES;j++)
{
if(same_digits(primes[i],primes[j])) //判断两个质数是否含有相同的数字
{
int diff = primes[j] - primes[i];
int last = primes[j] + diff; //等差数列第三个数
vector<int>::iterator it;
it = find(primes.begin(),primes.end(),last); //查找第三个数是否在primes中
if (it != primes.end()) //在primes中
{
if (same_digits(primes[i],last)) //含有相同的数字
{
cout<<primes[i]<<" "<<primes[j]<<" "<<last<<endl;
}
}
}
}
}
return 0;
}
程序输出为：
1487 4817 8147 2969 6299 9629
方法1 [思路同分析] 含相同数字的质数分成一组，判断每个小组是否满足存在三个元素形成等差。
首先将所有4位质数保存到primes列表中。
然后执行循环，只要primes不空，就取出primes[0]并转换为数字的列表，记为first，然后将first列表中的数字按从小到大排序，并将primes[0] 加入到小组gp中，然后从primes中删除，接着循环遍历primes找一个质数含有的数字与first相同，加入到gp中，并从primes中删除，遍历完成后，将小组gp保存到group中。跳出循环，所有的质数都已经分组了。
is_diff( item )函数判断列表item中是否含有三个数成等差，有则返回True，无则返回False.
最后，遍历groups，判断每个小组，(1)是否有超过3个元素，(2)是否有三个数成等差。
#coding=utf-8
from math import sqrt
def is_prime(n):
''' 判断n是否是质数 '''
if n <= 1:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, int(sqrt(n) + 1)):
if n % i == 0:
return False
return True
primes = [] # 保存所有四位数的质数
#找到所有四位数质数，并存放到primes列表中
for i in range(1000,9999):
if is_prime(i):
primes.append(i)
groups = [] #找到所有数字相同的质数，形成一个列表，并存放到groups中
while len(primes) > 0:
i, gp = 0, []
first = list(str(primes[0])) #第一个质数
first.sort() #转换为列表，并从小到大排序
gp.append(primes[0]) #添加到当前小组gp
primes.remove(primes[0]) #从primes中删除
while i < len(primes): #循环，找与第一个质数数字相同的所有质数，找到则加入到gp，并从primes中删除
list_i = list(str(primes[i]))
list_i.sort()
if list_i == first: #数字相同
gp.append(primes[i]) #加入当前小组
primes.remove(primes[i])#从primes中删除
i += 1
groups.append(gp) #保存当前小组
def is_diff(item):
''' 判断列表item中是否存在三个数等差 '''
length = len(item)
for i in range(0,length-2):
for k in range(i+1,length):
dif = item[k] - item[i] #dif 是前两个数的差
if item[k]+dif in item: #判断 第三个数是否存在在列表中
print '满足条件的三个数是：',item[i],item[k],item[k]+dif
return True
return False
#遍历每个小组，要求：(1) 至少含有三个质数，(2)能找到三个质数等差
for item in groups:
if len(item) >= 3: #（1）
if is_diff(item): #(2)
print '所在集合为：',item
程序的输出如下，可见只有两组满足题意，第一组题目中已经给出：
满足条件的三个数是： 1487 4817 8147 所在集合为： [1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741] 满足条件的三个数是： 2969 6299 9629 所在集合为： [2699, 2969, 6299, 9629]
296962999629
The series, 11 + 22 + 33 + … + 1010 = 10405071317.
Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.
Python的一行代码即可。但是C++处理起来就比较麻烦了。但是题目只要求给出结果的最后10位数字即可，问题就简单了，在整个计算过程中，只保留结果的最低10位数字即可，因为高位对结果不影响。保留低10位可以通过对10,000,000,000取模实现。
方法1 整个计算过程，中间结果对10,000,000,000取模，只保留最低的10位
#include <iostream>
using namespace std;
/************************************************************************
* 求n的n次方，结果对10,000,000,000取模，返回低10位
************************************************************************/
long long power(int n)
{
long long mul = 1;
for (int i=1;i<=n;i++)
{
mul *= n;
mul %= 10000000000; //取模，只保留最低的10位
}
return mul;
}
int main()
{
long long sum = 0;
for (int i=1;i<=1000;i++)
{
sum += power(i);
sum %= 10000000000; //取模，只保留最低的10位
}
cout<<sum<<endl; return 0;
}
方法1 直接法
print str(sum([i**i for i in range(1,1001)]))[-10:]
9110846700
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 x 7
15 = 3 x 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.
Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?
找到最靠前的四个连续的整数，它们都有四个不同的质因数（相同的算一个，如644中2² 算一个2）。
思路：这一题和上一题有很多类似处 Problem 46 Goldbach’s other conjecture。 上一题中的is_prime 和 primes_below 两个函数可以直接使用。只要将is_satisfied函数改变一下即可。为了方便阅读，下面完整描述具体的思路：
使用一个容器primes保存所有低于当前的数的质数。
is_prime(n)函数判断n是否是质数。
primes_below(n)函数将primes容器中最后一个质数+1到当前的数n之间的所有质数添加到primes中，如primes=[2,3,5]，n=9，则将5+1 到 9 之间的所有质数加入到primes中，即primes=[2,3,5,7]。
is_satisfied(n) 函数判断n是否有四个不同的质因数。方法是用n依次去除primes中的每一个质数p，如果能整除将结果存放到set集合factor中，然后n/=p，继续除p，如果不能整除，则p移动到primes中下一个质数。如果primes中每个质数都除过了，或者n==1时，跳出循环。如果跳出循环后，set集合factor中有四个元素，则表明n满足条件，返回True，否则返回False. Python代码如下
def is_satisfied(n):
''' 判断 n是否含有四个不同的质因数'''
cpy = n
primes_below(n) #所有小于n的质数
factors = set() #使用set可以保证保存的质因数不重复
i = 0
length = len(primes) #遍历质数表
while i < length:
if n % primes[i] == 0: #找到一个质因数
factors.add(primes[i])
n /= primes[i]
if n == 1: #n==1,跳出循环
break
else:
i += 1
if len(factors) == 4: #四个不同的质因数
print cpy, factors
return True
return False
主函数中，从最小的含有的四个不同质因数的数 i = 2 * 3 * 5 * 7 开始往后找，每找到一个满足is_satisfied()条件的i，即i有四个不同的质因数，则cnt++，如果cnt==4，则输出i-3；如i不满足is_satisfied()条件，则cnt 置 0。然后i++。
方法1 [思路同分析]
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
vector<int> primes;
/************************************************************************
* 判断n是否是质数
************************************************************************/
bool is_prime(int n)
{
if (n <= 1)
{
return false;
}
else if (n == 2 || n == 3)
{
return true;
}
else if (n % 2 == 0)
{
return false;
}
else
{
for (int i=3;i<=(int)sqrt((float)n);i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
}
/************************************************************************
* 将primes容器中的最后一个质数到n之间的所有质数，存放到primes中
************************************************************************/
void primes_below(int n)
{
int lower = 0;
int len = primes.size();
if (len > 0)
{
lower = primes[len - 1];
}
for (int i=lower+1;i<n;i++)
{
if (is_prime(i))
{
primes.push_back(i);
}
}
}
/************************************************************************
* 判断 n 含有4个不同的质因数
************************************************************************/
bool is_satisfied(int n)
{
primes_below(n); //先找到小于n的所有质数
int len = primes.size();
int cpy = n;
set<int> factors; //存放所有的质因数，不重复
int i = 0;
while(i < len)
{
if (n % primes[i] == 0) //找到一个质因数
{
factors.insert(primes[i]);
n /= primes[i];
if (n == 1)
{
break;
}
}
else
{
i++;
}
}
if (factors.size() == 4)
{
//cout<<cpy<<endl;
return true;
}
return false;
}
和 Python 方法1 基本相同。
方法1 [思路同分析]
from math import sqrt
def is_prime(n):
if n <= 1:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, int(sqrt(n) + 1)):
if n % i == 0:
return False
return True
primes = [] # store all the primes below the current number
def primes_below(n):
lower = 0
global primes
length = len(primes)
if length > 0:
lower = primes[lower-1]
#add primes between lower+1 and n into primes list
for i in range(lower+1,n):
if is_prime(i):
primes.append(i)
def is_satisfied(n):
''' check if n has four distinct prime factors '''
primes_below(n)
cpy = n
factors = set() #using set for remove the repeated factor
i = 0
length = len(primes)
while i < length:
if n % primes[i] == 0:
factors.add(primes[i])
n /= primes[i]
if n == 1:
break
else:
i += 1
if len(factors) == 4:
print cpy, factors
return True
return False
i = 2 * 3 * 5 * 7 # minimum number that has 4 distinct factors
cnt = 0
while True:
if is_satisfied(i):
cnt += 1
if cnt == 4:
print "found", i-3
break
else:
cnt = 0
i += 1
134043
【注：具体的质因数如下
134043 set([3, 491, 13, 7])
134044 set([47, 2, 31, 23])
134045 set([17, 83, 19, 5])
134046 set([11, 2, 3, 677])】
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
哥德巴赫的另一个猜想：一个合数可以写成一个质数+2倍的一个平方数 的和。这个猜想被证明是错误的，那么最小的一个满足该猜想的数是多少？
思路：使用一个容器primes保存所有低于当前的数的质数。
is_prime(n)函数判断n是否是质数。
primes_below(n)函数将primes容器中最后一个质数+1到当前的数n之间的所有质数添加到primes中，如primes=[2,3,5]，n=9，则将5+1 到 9 之间的所有质数加入到primes中，即primes=[2,3,5,7]。
is_satisfied(n)函数判断n是否符合猜想。用n依次减去primes中的质数（从后往前），剩下的数为remaining，如果remaining 是偶数，则继续将remaining除以2，赋给square，判断squrae是否是一个平方数，如果sqrt(square)是一个整数，则说明square是一个平方数，此时，说明n = 质数+2*squre，符合条件，返回True.
主函数从i=9开始，
方法1 [思路同分析] 从i=9开始往上，对每一个奇合数i，获取所以小于i的质数，用i依次减去质数，判断剩下的数是否是能写成一个平方的2倍。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> primes;
/************************************************************************
* 判断n是否是质数
************************************************************************/
bool is_prime(int n)
{
if (n <= 1)
{
return false;
}
else if (n == 2 || n == 3)
{
return true;
}
else if (n % 2 == 0)
{
return false;
}
else
{
for (int i=3;i<=(int)sqrt((float)n);i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
}
/************************************************************************
* 将primes容器中的最后一个质数到n之间的所有质数，存放到primes中
************************************************************************/
void primes_below(int n)
{
int lower = 0;
int len = primes.size();
if (len > 0)
{
lower = primes[len - 1];
}
for (int i=lower+1;i<n;i++)
{
if (is_prime(i))
{
primes.push_back(i);
}
}
}
/************************************************************************
* 判断 n 是否满足题目的哥德巴赫的另一个猜想
************************************************************************/
bool is_satisfied(int n)
{
primes_below(n); //先找到小于n的所有质数
int len = primes.size();
for (int i=len-1;i>=0;i--)
{
int remaining = n - primes[i]; //一个质数
if (remaining % 2 == 0 ) //2倍
{
int square = remaining / 2; //平方
float root = sqrt((float)square); //平方根
float round_root = (int)root;
if (root == round_root)
{
cout<<n<<"="<<primes[i]<<"+ 2 * "<<round_root<<"^"<<endl;
return true;
}
}
}
return false;
}
int main()
{
//判断每一个奇合数，是否满足条件
for (int i=9;;i+=2) // +2 保证奇数
{
if (!is_prime(i)) // 合数
{
if (!is_satisfied(i)) // 不满足猜想
{
cout<<"Found:"<<i<<endl;
break;
}
}
}
return 0;
}
方法1 [思路同分析] 从i=9开始往上，对每一个奇合数i，获取所以小于i的质数，用i依次减去质数，判断剩下的数是否是能写成一个平方的2倍。
from math import sqrt
def is_prime(n):
if n <= 1:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, int(sqrt(n) + 1)):
if n % i == 0:
return False
return True
primes = [] # store all the primes below the current number
def primes_below(n):
lower = 0
global primes
length = len(primes)
if length > 0:
lower = primes[lower-1]
#add primes between lower+1 and n into primes list
for i in range(lower+1,n):
if is_prime(i):
primes.append(i)
def is_satisfied(n):
''' check if n satisfied the conjecture '''
primes_below(n)
global primes
length = len(primes)
for i in range(length-1,-1,-1):
remaining = n - primes[i]
if remaining % 2 == 0:
square = remaining / 2
root = sqrt(square)
if root == int(root):
print n,'=',primes[i],'+ 2 *', root, '^'
return True
return False
i = 9
while True:
if not is_prime(i): #composite nubmer
if not is_satisfied(i):
print 'found:',i
break
i += 2 #odd number
5777
[上述代码可以获得其它小于5777的每个数的具体满足猜想的等式。]
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, …
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.
一个数既是三角形数，又是五边形数，同时又是六边形数。
思路：利用求根公式。
n(n+1)/2 = y 则 n = [sqrt(8y+1) – 1] / 2
n(3n-1)/2 = y 则 n =[sqrt(24y+1) + 1] / 6
n(2n-1) = y 则 n= [sqrt(8y+1) + 1] / 4
由于Tn、Pn、Hn中Hn 变化最快。所以从n=143 +1 开始，求出对应的y = Hn。然后将y带入其它两个公式的求根，如果根是整数，则表明y也是对应的类型的数（三角形数或五边形数）
方法1 从n=143+1开始，遍历Hn数列，利用求根结果，判断是否也满足其它两个数列
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n = 143 + 1;
while (1)
{
double h = n * (2 * n - 1); //Hn 六边形数
double t_root = (sqrt(1 + 8 * h) - 1) / 2;
double p_root = (sqrt(1 + 24 * h) + 1) / 6;
//h_root = (sqrt(1 + 8 * i) + 1) / 4;
double t = (int)t_root;
double p = (int)p_root;
//cout<<t<<" "<<p<<endl;
if (t == t_root && p == p_root)
{
long long result = n * (2 * n - 1); //直接输出double会使用e表示。所以使用long long
cout<<"n="<<n<<", h="<<result<<endl;
break;
}
n ++;
}
return 0;
}
方法1 [思路同分析] 遍历Hn数列，判断是否也满足其它两个数列
from math import sqrt
n = 143 + 1
while True:
h = n * (2 * n - 1)
t_root = (sqrt(1 + 8 * h) - 1) / 2
p_root = (sqrt(1 + 24 * h) + 1) / 6
#h_root = (sqrt(1 + 8 * i) + 1) / 4
if int(t_root) == t_root and int(p_root) == p_root: # and int(h_root) == h_root
print n,h
break
n += 1
1533776805
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
Find the sum of all 0 to 9 pandigital numbers with this property.
全排列问题。得到0~9的全排列，依次判断是否满足上面的条件，满足则加到sum
方法：得到一个0~9的全排列后，判断该数字是否符合条件，符合则加到sum中。
方法1 全排列+判断
注意: 这里的数必须使用long long类型
#include <iostream>
using namespace std;
long long sum = 0;
/************************************************************************
* 判断一个数digit是否满足条件
************************************************************************/
bool is_satisfied(int digit[])
{
int num = 0;
int d = 1;
int div[7] = {2,3,5,7,11,13,17};
for (d=0;d<7;d++) //d=1 -> d2
{
num = digit[1+d]*100 + digit[2+d]*10 + digit[3+d];
if (num % div[d] != 0)
{
return false;
}
}
return true;
}
/************************************************************************
* perm 产生 digit数组的所有排列，其中len是已经排列好的元素个数
************************************************************************/
void perm(int digit[],int len)
{
//所有的数都排列完成，得到一个排列，判断是否满足条件
if(len >= 10)
{
if (is_satisfied(digit))
{
long long value = 0;
long long ten = 1;
for(int i=9;i>=0;i--)
{
value += digit[i]*ten;
ten *= 10;
}
cout<<value<<endl;
sum += value;
}
}
//没有完全排好
else
{
//依次将后面的每一个数，排列到digit[len] 位置
for(int k=len;k<10;k++)
{
//交换 digit[k] 与 digit[len]
int tmp = digit[len];
digit[len] = digit[k];
digit[k] = tmp;
//继续递归下一层
perm(digit,len+1);
//交换位置还原
digit[k] = digit[len];
digit[len] = tmp;
}
}
}
int main()
{
int digit[10] = {0,1,2,3,4,5,6,7,8,9};
perm(digit,0);
cout<<"sum="<<sum<<endl;
return 0;
}
方法1 全排列 + 判断
def is_satisfied(digit):
''' Check if digit satisfied the conditions '''
num = 0
d = 1
div = [2, 3, 5, 7, 11, 13, 17]
for d in range(0,7):
num = digit[1+d]*100 + digit[2+d]*10 + digit[3+d]
if num % div[d] != 0:
return False
return True
result = 0
def perm(digit,length):
''' digit[0]~digit[length-1] already arranged '''
if length >= 10:
# all arranged, we get one permutation
if is_satisfied(digit):
print digit
global result
result += int(''.join([str(i) for i in digit])) #list to int
else:
for k in range(length,10):
#swap k and length
tmp = digit[length]
digit[length] = digit[k]
digit[k] = tmp
perm(digit,length+1)
#swap k and length back
digit[k] = digit[length]
digit[length] = tmp
if __name__=='__main__':
digit=[0,1,2,3,4,5,6,7,8,9]
perm(digit,0)
print result
16695334890
[符合条件的数共6个，分别为:
1430952867,1406357289,1460357289
4130952867,4106357289,4160357289
]
The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?
判断一个单词是不是三角单词，即该单词的所有字母对应的数字(A->1 B->2…)之和（成为单词的value）是不是一个三角数。三角数即n(n+1)/2 的数。
方法： 使用一个set集合将所有可能的三角数保存起来。所谓可能，就是小于words.txt中最长的单词的长度len和27的积。然后从words.txt中分割出每一个单词，统计它的value是不是在set中，在则表示是三角单词，计数+1.
方法1 [思路同分析] 使用vector和set存储，使用getline()分隔单词
read_data()函数读取words.txt中所有单词到vector容器words中，并且记录最长的单词的长度max_len。其中getline(fin,word,’,’) 从fin文件流中读取一行，以逗号, 为分割。
value(string word) 函数得到单词word的所有字母之和。
process() 函数统计三角单词数。首先，构造所有可能的三角数的集合triangle_numbers，上界是max_len * 27 ；然后遍历words，判断每一个单词是否在triangle_numbers中，在则cnt+1.
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <string>
using namespace std;
int max_len = 0; //最长单词的长度
vector<string> words; //保存所有单词
/************************************************************************
* 从文件中读取所有的单词到words容器中，并得到最长单词的长度max_len
************************************************************************/
bool read_words()
{
ifstream fin("words.txt");
string word;
while(getline(fin,word,',')) //,号分隔
{
//去除单词两边的引号，"HELLO" -> HELLO
word = word.substr(1,word.length()-2);
//记录最长的单词的长度
if(word.length() > max_len) max_len = word.length();
//保存到容器
words.push_back(word);
}
return true;
}
/************************************************************************
* 返回单词的值
************************************************************************/
int value(string word)
{
int sum = 0;
for (int i=0;i<word.length();i++)
{
sum += word[i]-'A' + 1;
}
return sum;
}
/************************************************************************
* 统计三角单词的数目
************************************************************************/
int process()
{
//构造所有可能的三角数的集合
int upper_limit = max_len * 27;
set<int> triangle_numbers;
for (int n=1;;n++)
{
int num = n*(n+1)/2;
triangle_numbers.insert(num);
if (num >= upper_limit) break;
}
//统计三角单词的个数
int cnt = 0;
for (int i=0;i<words.size();i++)
{
int v = value(words[i]); //得到单词的value
set<int>::iterator it = triangle_numbers.find(v); //查找集合
if (it != triangle_numbers.end()) //找到
{
cnt ++;
}
}
return cnt;
}
int main()
{
read_words();
cout<<process()<<endl;
return 0;
}
方法1 [思路同分析] 使用列表和set集合
download() 函数 从网上将words.txt文件下载到本地。process() 函数统计三角单词的数目，它首先从words.txt中读取所有的单词，然后去掉双引号”，然后根据，号分割出每个单词保存到words列表中，接着，构造了一个包含了所有可能三角数的set集合triangle_words，继而，判断每个words元素的值是不是在triangle_words中，在则cnt+1。最后输出cnt。ord()函数返回字母对应的ASCII码。
import os, urllib2
def download():
'''download the file words.txt'''
if os.path.isfile('words.txt'):
print 'File already Existed'
else:
#download
print 'Start Downloading...'
url = 'http://projecteuler.net/project/words.txt'
request = urllib2.Request(url)
response = urllib2.urlopen(request)
f = open('words.txt', 'w')
f.write(response.read())
f.close()
print 'Downloading OK'
def process():
'''do the process ,return the count of triangle words'''
#read from the file
f = open('words.txt', 'r')
content = f.read()
f.close()
#split out each word
words = content.replace(r'"','').split(',') # remove "" and then split by ,
#construct the set contains all the triangle number
max_len = max([len(i) for i in words]) #max length of all words
upper_limit = max_len * 27
n = 1
triangle_words = set()
while True:
num = n * (n + 1) / 2
triangle_words.add(num)
if num > upper_limit:
break
n += 1
print triangle_words
#count
cnt = 0
for w in words:
# ord('A') = 65 --> 1 = 65 - 64
value = sum([ord(i) - 64 for i in w])
if value in triangle_words:
cnt += 1
print 'count=',cnt
if __name__ == "__main__":
download() #download words.txt
process() #get the answer
162
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?
n最大为9，所以最大的pandigital是max_pan = 987654321。
判断一个数n是否是pandigital前面的题目已经遇到过很多回，可以借助set实现，方法是：(1)将n的各位数字保存到vector中，将vector保存到set中。(2) 判断vector和set的大小是否相等，不等则返回false，相等进入下一步。(3) 对vector默认排序sort。然后依次判断每一位是否是1,2,3…，如果有一个不相等则返回false，都相等则返回true。C++代码如下：
/************************************************************************
* 判断n是否是pandigital
************************************************************************/
bool is_pandigital(int n)
{
if(n<=0) return false;
vector<int> digits; //保存各位数字
while(n != 0)
{
digits.push_back(n%10);
n/=10;
}
set<int> set_n(digits.begin(),digits.end()); //转化为set，去重
int len = digits.size();
if(set_n.size() == len) //不含重复值
{
sort(digits.begin(),digits.end()); //默认从小到大排序
for (int i=0;i<len;i++) //digits=1,2,3...
{
if (digits[i] != (i+1))
{
return false;
}
}
return true;
}
return false;
}
找最大的pandigit的一种方法就是从max_pan往小遍历，如果找到这个数是质数，而且是pandigital，就输出结果，结束。不过这种方法会很慢。
另一种方法是，从n=9，即987654321 开始，往下找987654321的所有全排列。然后判断其是否是质数，一旦发现一个质数，则可以直接返回，因为它是最大的。如果没找到，则n=8，即87654321开始，重复上述过程。直到n=1时结束。这种方法的关键问题是全排列。
bool perm(s, length) 函数递归实现全排列。如perm(“987654321”，0)，递归实现987654321 从大往下的全排列。s存放序列，length表示序列中array[0]~array[length-1] 共length个元素已经排列好了。详见Python代码。
待续
方法1 找全排列，判断全排列是否是质数。
from math import sqrt
def is_prime(n):
if n <= 1:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0:
return False
else:
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True
def is_pandigital(n):
s = str(n)
set_n = set(s)
if len(s) == len(set_n):
lst = list(s)
lst.sort()
for i, item in enumerate(lst):
if int(item) != (i + 1):
return False
return True
else:
return False
max_pan_prime = 0
def perm(s, length):
''' s[0] - s[length-1] already arranged '''
if length >= len(s): #all arranged
n = int(s)
#print n
if is_prime(n) :#and is_pandigital(n)
global max_pan_prime
if n > max_pan_prime:
print 'find one answer:',n
max_pan_prime = n
return True
return False
else:
s_cpy = list(s)
for i in range(length, len(s_cpy)):
#swap(s_cpy[length],s_cpy[i])
tmp = s_cpy[length]
s_cpy[length] = s_cpy[i]
s_cpy[i] = tmp
if perm(''.join(s_cpy), length + 1): #True meaning found one, no need to do next
return True
#swap back
s_cpy[i] = s_cpy[length]
s_cpy[length] = tmp
#perm('987654321', 0)
pan = ['987654321','87654321','7654321','654321','54321','4321','321','21','1']
for i in range(0,9):
if perm(pan[i], 0): #return True,means that we found one answer
print 'max_pan_prime=', max_pan_prime
break #since we search from big to small, once found one answer, it's the biggest.
7652413
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021…
It can be seen that the 12th digit of the fractional part is 1.
If dn represents the nth digit of the fractional part, find the value of the following expression.
d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000
本题比较容易。C++中可以使用vector容器保存所有的数字，Python中直接使用字符串即可。
方法1 直接法。使用vector容器
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> digits; //保存所有的数字
digits.push_back(0); //从0开始，就不用考虑下标问题了
for(int i=1;i<100000;i++)
{
//将i的各位数字保存到digits容器中
int len=0;
int cpy=i;
int tmp[6];
while (cpy != 0)
{
tmp[len++] = cpy % 10;
cpy /= 10;
}
for (int k=len-1;k>=0;k--)
{
digits.push_back(tmp[k]);
}
}
cout<<digits[1]*digits[10]*digits[100]*digits[1000]*digits[10000]*digits[100000]<<endl;
return 0;
}
方法1 直接法。使用字符串
s = ''
for i in range(0,1000000):
s += str(i)
print int(s[1]) * int(s[10]) * int(s[100]) * int(s[1000]) * int(s[10000]) * int(s[100000])
210
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?
p 是直角三角形的周长，边为{a,b,c}。p =120 的直角三角形只有三种：{20,48,52}, {24,45,51}, {30,40,50}。
p ≤ 1000，找到一个p ，它的直角三角形种类最多。
思路：若{a,b,c}能形成周长为p的直角三角形，则 a+b+c = p； a2+b2=c2 。化简得：【1】p2 + 2ab = 2p(a+b) 。即满足【1】式的ab就是一个解。
求周长为p的直角三角形的种类数的方法为：a 为[1,p) ， b为[a,p)，c=p-a-b。这样就保证了a<=b<c。然后判断a,b是否符合【1】式，符合则是一个解，cnt++。
方法1 [思路同分析]
#include <iostream>
using namespace std;
/************************************************************************
* 满足周长为p的直角三角形的个数
************************************************************************/
int solution(int p)
{
int cnt = 0;
//a <= b < c
for (int a=1;a<p;a++)
{
for (int b=a;b<p;b++)
{
int c = p-a-b;
if (c>b)
{
if (p*p+2*a*b == 2*p*(a+b))
{
cnt++;
}
}
}
}
return cnt;
}
int main()
{
int max_p=0,max_cnt=0;
for (int p=1;p<=1000;p++)
{
int cnt = solution(p);
if( cnt > max_cnt)
{
max_p = p;
max_cnt = cnt;
}
}
cout<<max_p<<" "<<max_cnt<<endl;
return 0;
}
方法1 [思路同分析]
def solution(p):
print p
#a <= b < c
cnt = 0
#p*p + 2ab = 2p(a+b)
for a in range(1, p):
for b in range(a, p):
c = p - a - b
if c > b:
if p * p + 2 * a * b == 2 * p * (a + b):
#print a, b, c
cnt += 1
return cnt
max_p ,max_cnt = 0, 0
for p in range(1 ,1001):
cnt = solution(p)
if cnt > max_cnt:
max_p, max_cnt = p, cnt
print max_p, max_cnt
840
注：p=840，共有8种。分别为：
40 399 401 56 390 394 105 360 375 120 350 370 140 336 364 168 315 357 210 280 350 240 252 348
Take the number 192 and multiply it by each of 1, 2, and 3:
192 x 1 = 192
192 x 2 = 384
192 x 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?
可以由一个整数 x 与（1，2，…，n）的乘积连接而成的，只含有不重复的1~9 九个数字的数。
设乘数为 x，相当于至少 x 的位数 + 2*x 的位数要 <= 9 。当x是5位数时，x的位数 + 2*x 的位数 肯定>9，不满足。
确定了乘数x的范围后，可以穷举遍历。对每一个x，用product记录乘积的连接字符串。判断product是否满足条件即可。
方法1 【思路基本同Python方法1】使用vector容器保存数字，使用set容器去除重复数字。
split_digits(n,vector v)函数实现，将n的每一位数字，加入到容器v中。
乘数 x 从 1~10000遍历。对每一个x，做如下操作：
(1) 初始时split_digits(x,product)，将x的各位数字保存到product中。n = 2
(2) 将n*x的各位数字加入到product容器中。
(3) 判断product的长度，如果=9，说明可能满足条件，继续判断是否只含有1~9 九个数字，将product保存到set中，利用set去除重复的值。如果去除重复后的长度和原长度相等，说明不存在重复的值，再判断这九个数字不含有0即表明只含有1~9。至此找到一个满足条件的数了。如果product的长度 >9，说明x不用试了，肯定不能满足了，break，进入x+1。
程序打印出了所有满足条件的数，数量不多，所以可以直接看出最大值。
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;
/************************************************************************
* 将n的各位数字，加入到v容器
* n = 123,则分别将1，2，3 push_back 到vector容器v中
************************************************************************/
void split_digits(int n, vector<int>& v)
{
assert(n>0);
int digits[12];
int len = 0;
while(n!=0)
{
digits[len++] = n %10;
n /= 10;
}
for(int i=len-1;i>=0;i--) //digits[]为逆序保存
{
v.push_back(digits[i]);
}
}
void disp(int n){ cout<<n; }
int main()
{
for(int x=1;x<10000;x++)
{
vector<int> product;
split_digits(x,product); //x的各位数字加入到product中
//for_each(product.begin(),product.end(),disp);
//cout<<endl;
int n = 2;
while(1)
{
split_digits(n*x,product); //n*x 的各位数字加入到product中
if (product.size() == 9)
{
set<int> set_product(product.begin(),product.end()); //将product中的数字保存到set集合中
if(set_product.size() == 9) //说明没有重复数字
{
//判断是否含有数字 0
set<int>::iterator it = set_product.find(0);
if (it == set_product.end()) //不含数字0
{
//product是一个满足条件的值，输出
cout<<"x="<<x<<" n="<<n<<" product=";
for_each(product.begin(),product.end(),disp);
cout<<endl;
}
}
}
else if (product.size() > 9)
{
break; //跳出循环，进入x+1
}
else{}
n++;
}
}
return 0;
}
方法1 穷举判断
乘数 x 从 1~10000遍历。对每一个x，做如下操作：
(1) 初始时product=str(x)，n = 2
(2) product += str(n*x)
(3) 判断product的长度，如果=9，说明可能满足条件，继续判断是否只含有1~9 九个数字，将product保存到set中，利用set去除重复的值。如果去除重复后的长度和原长度相等，说明不存在重复的值，再判断这九个数字不含有0即表明只含有1~9。至此找到一个满足条件的数了。判断找到的product是否最大，并记录最大到max_product中。如果product的长度 >9，说明x不用试了，肯定不能满足了，break，进入x+1。
max_x, max_product = 0, 0
for x in range(1, 10000):
product = str(x)
n = 2
while True:
product += str(n * x)
if len(product) == 9:
set_product = set(product) # set is used to remove the repeated digits
if len(set_product) == 9:
#find one candidate
#check if has '0'
if '0' in set_product:
pass
else:
print 'find one: x=', x, ' n=', n, ' product=', product
if int(product) > max_product:
max_x, max_product = x, int(product)
elif len(product) > 9:
break
else:
pass #do nothing, continue the loop
n += 1
print max_x, max_product
932718654
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
可截断的质数。一个质数，左移截断和右移截断的结果也是质数，则称这个数是可截断的质数。如3797，左移截断结果3797, 797, 97, 7 都是质数，右移截断结果3797, 379, 37, 3 也都是质数。
方法：对于Python，左移截断和右移截断比较简单，通过字符串的切片操作完成即可。对于C\C++，可以通过数值分析来实现：左移相当于除10，右移相当于对低位取模。
如：3797
左移，3797 / 10 = 379； 379 / 10 = 79; 79/10 = 9
右移，3797%1000 = 797；3797%100 = 97；3797%10 = 7；
方法1 左移除10，右移取模。
#include <iostream>
#include <cmath>
using namespace std;
/************************************************************************
* 判断n是否是质数
************************************************************************/
bool is_prime(int n)
{
if(n <= 1) return false;
if(n == 2 || n == 3) return true;
else if (n % 2 == 0) return false;
else
{
for(int i=3;i<(int)sqrt((float)n)+1;i++)
{
if(n % i == 0) return false;
}
}
return true;
}
/************************************************************************
* 判断n是否满足左移右移都是质数
************************************************************************/
bool truncatable(int n)
{
if (n<=0) return false;
//计算n的长度
int len = 0;
int cpy = n;
while (cpy !=0)
{
len ++;
cpy /= 10;
}
//右移，相当于每次除10
cpy = n;
while (cpy !=0)
{
//cout<<cpy<<endl;
if(!is_prime(cpy)) //一旦不是质数，直接返回false.这里多判断了一次n本身是否是质数。
{
return false;
}
cpy /= 10; //右移一位，相当于移除了个位。
}
//cout<<"-----------"<<endl;
//左移，相当于每次取低位的模 123，123%100 = 23；123%10 = 3；
cpy = n;
while(len>1)
{
int x = cpy % (int)pow((float)10,len-1); //低位取模
//cout<<x<<endl;
if (!is_prime(x))
{
return false;
}
len--;
}
return true;
}
int main()
{
int cnt = 0,sum=0,i=8;
while(cnt< 11)
{
if (truncatable(i))
{
sum += i;
cnt ++;
cout<<i<<endl;
}
i++;
}
cout<<sum<<endl;
return 0;
}
方法1 转换为字符串，然后使用字符串切片完成左移和右移。
from math import sqrt
def is_prime(n):
if n <= 1:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0:
return False
else:
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True
def truncatable(n):
flag = True
#to left
s = str(n)
for i in range(1,len(s)):
s1 = s[i:]
if not is_prime(int(s1)):
flag = False
if not flag:
return False
#to right
s = str(n)
flag = True
for i in range(len(s)-1,0,-1):
s1 = s[:i]
if not is_prime(int(s1)):
flag = False
if not flag:
return False
else:
return True
i, cnt, sum = 10, 0, 0
while cnt < 11:
if is_prime(i) and truncatable(i):
sum += i
print 'find:',i
cnt += 1
i += 1
print 'sum=', sum
748317
这11个数是：23，37，53，313，317，373，797，3137，3739，739397
The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
一个数，二进制和十进制都是回文数。求100,000以内所有这样的数的和。
方法：C++数制转换这篇博客中，我已经实现了各种进制之间的转换，当然包括了十进制转化为二进制。这个思路在C\C++和Python中都可以使用。思路如下，通过不断的%x 再 /= x来转换为x进制。
//十进制转x进制
while(dec != 0){
chs[i] = dec%x+'0';//int转char
dec /= x;
}
//再将chs逆置即可
while循环结束后，chs保存的实际上是逆序的，需要再逆序回来。(也可以使用stack或者deque的头插来实现，就不需要逆序了)
Python 中还提供了bin函数，可以直接将10进制转换为2进制。
至于判断回文，都可以现将整型转换为字符串，然后判断字符串逆置后是否相等。
方法1 通过 n%2 再 n /= 2 循环来转换为二进制，使用deque容器（替代数组）实现回文的判断
#include <iostream>
#include <algorithm> #reverse_copy()
#include <deque>
using namespace std;
/************************************************************************
* 十进制转换为二进制
* 将十进制数n，转换为二进制字符串，存放到bin中。如n=123，bin={1,2,3}
************************************************************************/
void decimal2binary(int n,deque<int>& bin)
{
if(n<=0)
{
bin.push_front(0);
return;
}
while(n != 0)
{
bin.push_front(n%2); //头插
n /= 2;
}
}
void disp(int elem){cout<<elem;}
/************************************************************************
* 判断n 的十进制和二进制是否都是回文数
************************************************************************/
bool is_palindromic_both(int n)
{
if (n<=0)
{
return false;
}
//////////////////////////////////////////////////////////////////////
//判断十进制是否是回文数
//获取十进制的各位数字
int cpy = n;
deque<int> digits; //存放各位上的数字
while (cpy!=0)
{
digits.push_front(cpy%10);
cpy /= 10;
}
//逆置
deque<int> digits_rvs(digits.size()); //逆序存放各位上的数字
reverse_copy(digits.begin(),digits.end(),digits_rvs.begin()); //逆置
//判断正序和逆序是否相等
bool flag = true;
deque<int>::iterator it1,it2;
for (it1=digits.begin(),it2=digits_rvs.begin();it1!=digits.end() && it2!=digits_rvs.end();it1++,it2++)
{
if (*it1 != *it2)
{
flag = false;
break;
}
}
//十进制不是回文，直接返回false
if(!flag)
{
return false;
}
//////////////////////////////////////////////////////////////////////
//判断二进制是否是回文数
deque<int> bin; //存放二进制
decimal2binary(n,bin);
//逆序
deque<int> bin_rvs(bin.size()); //存放二进制逆序
reverse_copy(bin.begin(),bin.end(),bin_rvs.begin());
//判断正序和逆序是否相等
flag = true;
for (it1=bin.begin(),it2=bin_rvs.begin();it1!=bin.end() && it2!=bin_rvs.end();it1++,it2++)
{
if (*it1 != *it2)
{
flag = false;
break;
}
}
//二进制是否回文
if(flag)
{
return true;
}
else
{
return false;
}
}
int main()
{
int sum = 0;
for (int i=1;i<1000000;i++)
{
if (is_palindromic_both(i))
{
sum += i;
}
}
cout<<sum<<endl;
return 0;
}
方法1 通过 n%2 再 n /= 2 循环来转换为二进制
def decimal2binary(n):
'''convert decimal n to binary '''
bin = []
if n <= 0:
return [0]
while n != 0:
bin.append(str(n%2))
n /= 2
bin.reverse()
s = ''.join(bin)
return s
print decimal2binary(8)
def is_palindromic_both(n):
'''check if n is palindromic in both decimal and binary '''
dec = str(n) #decimal
rvs_dec = dec[::-1]
bin = decimal2binary(n) #binary
rvs_bin = bin[::-1]
return (dec == rvs_dec and bin == rvs_bin)
#result
print sum([i for i in range(1, 1000000) if is_palindromic_both(i)])
方法2 使用bin()函数实现10进制转2进制
用bin()函数替换decimal2binary() 函数即可。其它一样。注意去掉bin()返回的二进制前的前缀0b。
872187