华为实习生面试归来

实验室被分成了几波人,有早上很早去的,有11点去的,还好我是下午3点的面试。早上还可以再临阵磨枪一下。

接受上次实验室去阿里面试回来的优秀芳的经验,特意按照简历上的内容做了最后的巩固,试图将简历上上提到的再温故一遍,因为好多已是很久之前的经历了。比如本科的那些项目和比赛的事情,过去好几年了已经。

技术方面,我在简历上侧重就写了数据库、C\C++,STL,MFC,Python,网络编程等几项,因为这是我这次面试的重点,其它的接触过的语言或技术都作为兴趣,并没有体现在简历上。

由于2:30会有车在地铁出口等待,我和优秀芳在1点还没到就出发,踏上开往西兴的地铁。到达时,刚刚2点。等到了2点半的时候等到了车,一起去了华为公司。3点面试的一共有15个,我们在那边等了一会,然后就几个几个的被HR带到二楼进行面试。 面试前,我已经从早上面试完的同学那里获知了大概的流程,共两轮面试,所以还是有些普的,不过,可能是太久没有经历这样的面试体验了,有些些的小激动和紧张,很不自觉的,有些尴尬。

不过再多的不安和紧张,在进入面试厅的时候就消失了。也许很多人都是这样的,最紧张的往往是等待事情发生的过程,当正真到来的时候,整个人就会静下来,接受一切。

面试我的面试官年纪不大,看上去挺温和。说声“老师您好”后边坐在了他的对面。首先是自我介绍,事先都有准备的,也就说的还算通畅,主要是罗列一下自己的经历,提一些自己的优势。随后就是技术相关的面试,问了数据库、异步网络编程、C++11标准等几个问题,还有为什么来华为。交谈的还是比较融洽的。

一面结束,我就出去在另一个休息厅,等待二面。此刻,心里轻松多了。回想了些自己刚刚的表现,觉得也没有什么遗憾之处,该说的都说了。

等了有近十分钟,才有HR叫我,带我去休息对面的另一个厅接受二面。听我同学说,二面是boss面,所以面试官看上去挺严肃的。首先还是自己介绍,然后问了些个人问题,比如哪里人,为什么从西安回到杭州。然后让我介绍一个自己比较熟的项目,我就把WSN环境监控的那个介绍了一遍。然后问我项目中遇到的问题,我就把数据库存储和并发访问提出来了,自我感觉回答的一般般,表达的不是很理想。之后又问我对华为有什么了解。我就把一面的回答重新组织了一下。之后,面试官说那就这样结束吧,可以回去了。二面又很快结束了。

————————————————————————————————————————————————-

总结一下,提前做好准备是很有必要的,准备的越充分,表现的会越自信。还是要调整好自己的心态,今天没面试前那几分钟,有些紧张和沉重,或许是好久来的第一次吧,这样不好,以后还是要尽量放轻松嘛,自信点吧。

期待收到下一步的通知啊

阿里实习生笔试归来

笔试安排在浙大的玉泉校区,时间是昨天晚上6:30~8:30,周六晚上,这个时间点不得不说给很多人带来了不便,不知道是出于什么考虑。很早就投了简历,安排是29号全国统一笔试,等到笔试前两天才收到短信,开始还惶惶的以为要刷人。

有几个同学分在了不同的教学楼,看来这次的规模真的很大。我所在的考场不大,共52个人,我就是51号,不过这个数字我还挺满意的,因为每个位置上放的编号卡片上有写这是51job组织的,51job,51号,不错,很有意义。

回到正题吧,考场中有两个监考,考试提供一张答题卡、一份7页的试卷、一张稿纸。感觉好久都没有体验这样正规的考试了,上一次还是2年前吧,这样的氛围让人觉得靠谱。2个小时的时间,7页的试卷,一共29道题目,分为单选20道,不定项选择4道,填空与问答题5道。当然最后第7页还有一道Java选做题,这像是阿里笔试题的一个传统似的,之前也是如此。我不搞Java,所以最后一题瞟了一眼,没有写,把时间都放在了前面。

单选

单选20道,涉及网络(1题,划分子网)、操作系统(1题,linux系统磁盘查看大小问题)、概率题(1题,生女孩问题)、逻辑题(2题,找假钱问题和市场客户问题),剩下的就是编程中的一些具体问题,包括快排的时间复杂度序、递归、二叉树度问题、栈的出栈顺序等。选几题觉得有些意义的题回忆一下吧。

第4题: C语言程序运行在32位操作系统上,x和z是int型,y是short型,x=127,y=-9.  执行z=x+y 之后,x,y,z各是多少(十六进制表示)?

计算机中整数是以补码形式存储的,正数的补码与原码相同,负数的补码等于原码取反(不包括符号位)+1

执行 z = x + y,x 和 y 运算前后不变,x为正数,所以x=0x0000007F。

y为short型-9,原码为1000 0000 0000 1001,最高位符号位为1表示负数,其补码为1111 1111 1111 0110 + 1 = 1111 1111 1111 0111 = 0xFFF7。所以 y=0xFFF7。

z = x+y = 127-9=118,补码表示为 z = 0x00000076

第8题:下面C++代码的输出是___?

void fun(char *x)
{
	x++;
	*x = 'a';
}

int main()
{
	char str[sizeof("hello")];
	strcpy(str,"hello");
	fun(str);

	cout<<str;
	return 0;
}

这一题的关键是sizeof(“hello”) 值是多少。”hello” 是一个字符串,系统会自动在后面添加一个’\0’,所以sizeof(“hello”) 等于6。后面的就好理解了。fun函数无非将第二个字符转换为a,所以程序的输出为hallo。

第16题:年轻人花80元买老板的原件160的物品,年轻人没有零钱,给了张100的,老板也没有零钱,就接过年轻人的100元去隔壁兑换了零钱,然后找给了年轻人20元。但是事后,隔壁过来说100元是假的,老板不得不赔给隔壁100元。请问,整个事件中,老板损失了多少钱?

不要被问题的花花绕的一大圈弄混了。抓住关键点:隔壁没有损失,老板的损失也就是年轻人赚到的钱。年轻人赚了65元的物品和20元的现金。所以老板损失65+20=85元。

第17题:2100 mod 7 = ?

找规律 21 mod 7 = 2; 22 mod 7 = 4; 23 mod 7 = 1; 24 mod 7 = 2; 25 mod 7 = 4 …

所以规律是:2-4-1 循环,所以 2100 mod 7 = 21 mod 7 = 2;

第11题: 给了一个含有递归的函数fun(),问在通常的机器上运行,fun(35)的运行时间大概是多少?  

int f(int x)
{
	int s = x;
	while(s-- > 0) s += fun(x);
	return max(s,1);
}

可选项是几毫秒,几秒,几分种,几个小时。

这题我到时没有做出来,感觉应该是n!+(n-1)! … 的复杂度,就猜了一个几分钟。具体的,等我再想想。

第15题:给了一个有向图,求起点到终点的最大流量。(这题我还不太懂,待学习

多选(21~24)

第21题是关于malloc和free的一些理解。判断下面的说法是否正确:

(1) 无法通过malloc(size_t)函数调用申请超过机器物理内存大小的内存块。

首先,通过查找资料[12],得出结论:malloc() 分配的是虚拟内存,访问具体虚拟地址的时候,实际上会做虚拟内存和物理内存的映射,最终调用物理地址的内容。

所以我觉得可以通过malloc(size_t)申请超过机器物理内存大小的内存块,因为机器存在虚拟内存。(1) 错误。 【我不是太确定】

(2) 无法通过内存释放函数free(void*)直接将某块已经使用完的物理内存直接还给操作系统。

资料[3] 中提到:

其中brk区(确切名字我不知道)可以用系统调用brk动态增长或缩小,malloc/free动态分配的内存就在brk区,内存分配算法由C库函数实现,与操作系统无关。需要更多内存时,调用sbrk/brk增长brk区,malloc一般不对应一次brk,一次brk分配比较大的块,malloc在这里再分,free一般只是更新空闲块,不调用任何系统调用,就是说free释放的内存可能不归还给系统,直到进程退出时才释放。

free释放的内存不一定直接还给操作系统,可能要到进程结束才释放。但(2) 说free不能把它归还给操作系统,就不对了。所以,我认为(2)是错误的。

(3) 可以通过内存分配函数malloc(size_t)直接申请物理内存

通过前面两题的,可以直到malloc不能直接申请物理内存,它申请的是虚拟内存。所以我认为(3)是错误的。

填空和简答题 (25~29)

第25题是数据传输问题。给了一副画面的分辨率,画面的像素位深,每秒的传输帧数,然后已知蓝牙的最大带宽,问能不能通过蓝牙传输。

这题比较简单,简单算一下每秒传输的数据量,比较一下与蓝牙带宽的大小即可。

第26题:将N条长度为M的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为____?

两两归并排序。

第一次,N/2 组,每组时间复杂度O(2M),综合为 O(N/2 * 2M) = O(NM)

第二次,N/4 组,每组时间复杂度O(4M),综合为 O(N/4 * 4M) = O(NM)

依次类推,共有logN (底为2)次。

故总的时间复杂度为:O(MNlogN)

第27题: ABCD四人要在夜里过桥,分别耗时1、2、5、10分钟,只有一个手电筒,并且同时最多两人一起过。请安排方案让四人都过,用时最短,给出方案。

这题,我当时没有想到好方法。以为满足贪心算法,就让A每次来回接送。共耗时19分钟。

但是,刚刚我搜free 和 malloc时,发现了已经有人把昨晚的题目都放出来了。同时也给了他的解答,速度真快,让我佩服!

2014.3.29 阿里巴巴 实习校招 笔试 题目及部分参考答案

他对于本题的答案是17,方法是:1、2先过,2留下1回来,5、10再过,2回来,1、2再过。

比我的要优。看来我这题悲剧了。

第28题:下列代码是实现有序整数数组的二分查找,请指出其中的bug。

int binary_search(int *array, int length, int key)
{
	int start = 0, end = length - 1;
	while (end > start)
	{
		int middle = (start + end) / 2;
		int tmp = array[middle];
		if (tmp < key)
			start = middle;
		else if (tmp > key)
			end = middle;
		else
			return middle;
	}
	return -1;
}

我认为这里面存在1个bug和2个可改进的地方。

1个bug:  end > start 改为 end >= start。 前者会丢掉array长度为1,且array[0]就是要查找的元素的情况。

2个可改进:start = middle 改进为 start = middle +1  因为middle也是不可能的。同理 end = middle 改进为 end = middle -1.

第 29 题,跳跃链表,求时间复杂度。

完全不会。我就猜它和二叉排序树(nlogn)差不多,然后利用上概率p进行改进,所以猜它的时间复杂度为O(nplogpn),完完全全是猜的啊。

————————————————————————————————————-

总的来说,本次笔试,我对阿里的印象还不错,组织的正规,题目也有难度,有广度,有深度,有区分,像个搞技术的大公司的笔试题。对自己的答题,只能说能做的我都做了,确实自己存在一些知识点不知道,有待学习。

Problem 35 Circular primes

Problem

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

分析

一个数,它本身是质数,各位经过旋转后也是质数,求1,000,000以下满足这种条件的数的个数。

思路:使用is_prime()判断一个数是否是质数,使用is_circle()判断一个数向右旋转所得的几个数是否也是质数。如果is_prime() 和 is_circle()同时满足,就找到了一个,cnt++。最后输出cnt即可。

判断质数的is_prime()已经写过很多次,故本题的关键在于如何旋转一个数,判断每个向右旋转所得得数是否都是质数。

如果是Python,可以先将数n转换为字符串,s = str(n) 【如s=’123’】,然后对s进行len(s)-1【 2 】 次向右旋转,每次右移一位,可通过切片操作实现:s = s[-1:] + s[:-1] 【s=最后一个元素+开头到倒数第二个元素】,得到旋转后的数【’312’,’231’】,使用is_prime()判断旋转所得数是否是质数。

如果是C\C++,可以通过将数的个位放到数的最高位来实现向右旋转一位。如n=123,位数为 len=3,个位为bit=n%10=3,将n右移一位腾出最高位 n = n/10 = 12。将个位乘上10len-1, 然后加到n上,n = n + bit* 102 = 12+300=312。这个过程用rotate_one_bit(int n) 函数实现。

C\C++

方法1  [思路同分析] 个位放到最高位实现右旋一位。从i=1~1,000,000依次判断是否是质数且右旋的结果都是质数。

#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 向右旋转一位
 ************************************************************************/
int rotate_one_bit(int n)
{
	int i=0;
	int len=0;     //n的位数

	//获取n的位数 len
	int cpy = n;
	while(cpy!=0)
	{
		len ++;
		cpy /= 10;
	}

	//获取个位数字 bit
	int bit = n % 10;

	//将n右移一位,即/10
	n /= 10;

	//将个位补到最高位
	n += bit * (int)pow((float)10,len-1);

	//cout<<n<<endl;
	return n;
}

/************************************************************************ 
 * 判断n的每个旋转所得的数是否都是质数
 ************************************************************************/
bool is_circle(int n)
{
	if (n == 0) return false;

	//判断n中是否含有 '0',随便计算出n的位数
	int cpy = n;
	int len = 0;
	while (cpy!=0)
	{
		len ++;
		if (cpy % 10 == 0) //出现'0'
		{
			return false;
		}
		cpy /= 10;
	}

	//判断旋转所得的数是否都是质数  
	for (int i=1;i<=len-1;i++)    //向右旋转len-1次
	{
		n = rotate_one_bit(n);
		if (!is_prime(n))         //某个旋转结果不是质数
		{
			return false;
		}
	}
	return true;
}

int main()
{
	int cnt = 0;
	for (int i=1;i<1000000;i++)
	{
		if (is_prime(i))
		{
			if (is_circle(i))
			{
				cnt ++;
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}

 

Python

方法1 [思路同分析] C\C++方法1的Python版

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_circle(n):
    if is_prime(n):
        if '0' in str(n):
            return False
        p = []   #[['1', '2', '3'], ['1', '3', '2'],..., ['3', '1', '2']]
        perm(list(str(n)),0,p)
        flag = True
        for i in p:
            a = int(''.join(i)) #['1', '2', '3'] -> '123' -> 123
            if not is_prime(a): #one rotation of n is not prime
                flag = False
                break
        if flag:
            return True
    return False

def is_circle(n):
    if is_prime(n):
        if '0' in str(n):
            return False
        s = list(str(n))
        for i in range(1,len(s)):#rotate len(s) counts
            s = s[-1:] + s[:-1] #rotate s by one bit
            a = int(''.join(s))
            if not is_prime(a):
                return False
        return True
    return False

result = []
for i in range(1,1000000):
    if is_circle(i) and is_prime(i):
        result.append(i)
        print i
print result
print len(result)

答案

55

这个55个数字是:2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331

知识点

  • Python 切片实现右旋一位: s = s[-1:] + s[:-1]
  • C\C++ 通过将个位移动到高位实现右旋一位

Problem 34 Digit factorials

Problem

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

分析

一个数等于它各位数字阶乘的和。求所有这样的数的和。

每增加一位数字,阶乘最多增加9!= 362,880。对于一个满足条件的数:
如果它是6位数,阶乘之和最大为 6*9! = 2177280 > 最大的6位数999,999,所以可能
如果它是7位数,阶乘之和最大为 7*9! = 2540160 < 最小的7位数1,000,000,所以不可能
所以满足条件的数,最多是个6位数

思路:有了上面的分析,就可以穷举遍历了。对与每个i = 3~999,999,计算其各位数字阶乘之和,如果等于i,则满足条件,进行累加。

C\C++

方法1 穷举遍历

#include <iostream>
#include <vector>

using namespace std;

/************************************************************************ 
 * 返回n!
 ************************************************************************/
int factorial(int n)
{
	int i=1,result=1;
	while (i<=n)
	{
		result *=  i++;
	}
	return result;
}

/************************************************************************ 
 * 返回n的各位数字的阶乘之和
 ************************************************************************/
int digit_factorial(int n)
{
	int a=0,sum = 0;
	while (n!=0)
	{
		sum += factorial(n % 10);
		n /= 10;
	}
	return sum;
}

int main()
{
	vector<int> result;
	for (int i=3;i<=999999;i++)
	{
		if(digit_factorial(i) == i)
		{
			result.push_back(i);
		}
	}

	int sum=0;
	vector<int>::iterator it;
	for (it=result.begin();it!=result.end();it++)
	{
		sum += *it;
	}
	cout<<sum<<endl;
	return 0;
}

Python

方法1 穷举遍历

#return n!
def f(n):
    if n==0 or n==1:
        return 1
    return reduce(lambda x,y: x*y, range(1,n+1))

result = []
for n in range(3,999999):
    sm = sum([f(int(i)) for i in str(n)])
    if sm == n:
        result.append(n)
print result
print sum(result)

答案

40730

两个符合条件的数为 145, 40585

Problem 33 Digit canceling fractions

Problem

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

分析

49/98 = 4/8  通过删除9,所得结果也是正确的。找到分子分母都是2位数(分子小于分母),且满足这种条件的(即ab/bc = a/c  )数,这样的分数共有4个。求这个四个分数的乘积最后约分简化后的分母。

思路:很直接,通过穷举判断即可。

C\C++

方法1 穷举遍历

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main(int argc, _TCHAR* argv[])
{
	vector< pair<int,int> > result;
	for (int a=10;a<=98;a++)
	{
		for(int b=a+1;b<=99;b++)
		{
			if (a%10 == b/10)//分子个位==分母十位
			{
				if (b%10 != 0)
				{
					if (a/(float)b == (a/10)/(float)(b%10) )//删除相同的数字后,仍相等
					{
						pair<int,int> p(a,b);
						result.push_back(p);
					}
				}
			}
		}
	}

	int up=1,down=1; //记录四个分数分子和分母分别的乘积
	vector<pair<int,int> >::iterator it;
	for (it=result.begin();it!=result.end();++it)
	{
		up *= it->first;
		down *= it->second;
	}

	//对乘积的分子分母约分
	for (int i=up;i>1;i--)
	{
		if (up%i==0 && down%i==0)
		{
			up /= i;
			down /= i;
			break;
		}
	}
	//输出最后的分母
	cout<<down<<endl;
	return 0;
}

Python

方法1 穷举遍历 [C\C++方法1的Python版]

result = []  # store the four fraction

#find the four fraction
for numerator in range(10,99):
    for denominator in range(numerator+1,99):
        if numerator%10 ==  denominator/10:
            a = numerator/10
            b = denominator%10
            if b != 0:
                if float(numerator)/denominator == float(a)/b:
                    #print a,b,numerator,denominator
                    result.append((numerator,denominator))
print result

#product of the four fraction
up, down = 1, 1
for item in result:
    up *= item[0]
    down *= item[1]

#simplify the final fraction
for i in range(up,1,-1):
    if up % i == 0 and down % i == 0:
        up /= i
        down /= i
        break
print down

答案

100

Problem 32 Pandigital products

Problem

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, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

分析

Pandigital 是一个n位的数,它刚好由数字1~n组成。 39 x 186 = 7254,被乘数、乘数、积刚好由1~9组成,7254就是满足条件的一个积。求所有满足这种条件(即被乘数、乘数、积刚好由1~9组成)的积的和。

如果 a * b = c 中c满足条件,假设a<b,则必然 a<b<c。因为a,b,c的位数总共等于9,所以a必然小于3位数(100*100=10000 共11位 > 9位)。所以a的范围最多为[1,98]。 a至少为1为,则b和c总共最多为8位,b<c,所以b最多为4位。所以b的范围为[a+1, 9876]。

有了a和b的范围,下面就是穷举遍历+判断了。为了确保数据的不重复,使用set来存储。

C\C++

方法1 遍历 + 判断

使用itoa() 将 数字转换为字符串,使用is_unique(char* s) 判断字符串s是否不含’0’且不含重复字符。

a 从1~98,b从a+1 ~9876。对每个满足is_unique()的a和b,计算c, 把a,b,c使用strcat连接成一个字符串,判断是否满足is_unique而且长度为9,满足则c是一个值,放入set集合 result中。

最后累加result中的值,得到结果。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring> //strlen strcat
#include <cstdlib> //itoa

using namespace std;

/************************************************************************ 
 * 判断s是否含有'0' 或者重复的字符
 ************************************************************************/
bool is_unique(char* s)
{
	int len = strlen(s);
	char* p = find(s,s+len,'0');

	if (*p != '\0') return false;  // 存在'0'

	set<char> chs;
	for (int i=0;i<len;i++) chs.insert(s[i]);

	//vector<char> chs;              //char* 存放到vector中
	//for (int i=0;i<len;i++) chs.push_back(s[i]);
	//sort(chs.begin(),chs.end());   //排序
	//unique(chs.begin(),chs.end()); //去除重复的值

	return len == chs.size();      //有无重复值被移除
}

int main()
{
	set<int> result;
	char buf_a[3];
	char buf_b[5];
	char buf_c[16];
	int c = 0;

	for (int a=1;a< 99;a++)
	{
		if (is_unique(itoa(a,buf_a,10)))       //a 不含'0' 或重复数字
		{
			for (int b=a+1;b<9877;b++)
			{;
				if (is_unique(itoa(b,buf_b,10)))//b 不含'0' 或重复数字
				{
					c = a * b;
					itoa(c,buf_c,10);

					//abc 总长度 > 9, 不符合,continue
					if ((strlen(buf_a) + strlen(buf_b) + strlen(buf_c)) > 9) continue;

					if (is_unique(buf_c))//c 不含'0' 或重复数字
					{
						strcat(buf_c,buf_b);
						strcat(buf_c,buf_a);
						cout<<a<<" * "<<b<<" = "<<c<<"   "<<buf_c<<endl;
						if ( is_unique(buf_c) && (strlen(buf_c) == 9) )
						{
							cout<<a<<" * "<<b<<" = "<<c<<endl;
							result.insert(c);
						}
					}
				}
			}
		}
	}

	//cout<<result.size()<<endl;
	set<int>::iterator it;
	int sum = 0;
	for (it = result.begin();it!=result.end();++it)
	{
		sum += *it;
	}
	cout<<sum<<endl;
	return 0;
}

Python

方法1 [C\C++方法1 的Python版]

def is_unique(s):
    ''' whether s has two same digits '''
    if '0' in s:
        return False
    len1 = len(s)
    len2 = len(set(s)) #using set to unique
    return len1 == len2

result = set()
for a in range(1, 99):    #[1,99)
    if is_unique(str(a)):             #digits of a is unique
        for b in range(a+1, 9877):
            if is_unique(str(b)) and is_unique(str(a) + str(b)):   #digits of b is unique
                c = a * b
                s = str(a)+str(b)+str(c)
                if is_unique(s) and len(s) == 9:  #multiplicand,multiplier,product is 1 - 9
                    #print a,b,c
                    result.add(c)
#print result
print sum(result)

答案

45228

知识点

  • 通过set集合,去除重复数据

Problem 31 Coin sums

Problem

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

分析

找钱问题。已知的面值为1,2,5,10,50,100,200,用这些面值去凑200,求有多少种凑法。

思路:一个直接的思路就是先用大面值再用小面值,依次去寻找。

先用 200面值 去凑 200,如果用 0 个200面值,则问题转换为再用100面值 去凑剩下的200-0*200=200。如果用1个200面值,则问题转换为再用100面值 去凑剩下的200-1*200=0 。可见这里面存在一个递归关系。

C\C++

方法1 递归求解

使用value[8] 保存记录面值1,2,5…,200;cnt[8] 保存对应的每种面值使用的数量;solutions用来保存可以凑到200的方案总数。Check(int v,int remaining) 函数实现递归关系,它使用面值value[v]去凑钱remaining,依次使用i= 0~remaining/value[v] 个该面值,然后递归调用Check(v-1, remaining-i*value[v] )去凑剩下的钱。如果v==0,说明要使用最后一种面值,即面值1去凑,此时直接用remaining个面值1即可,然后输出结果。如果remaining==0,说明前面已经凑到200,不用再凑了,将cnt[0~v] 设为0 ,然后输出结果即可。

#include <stdio.h>

int value[8] = {1,2,5,10,20,50,100,200};  //面值 排序 v: 0 ~ 7
int cnt[8] = {0,0,0,0,0,0,0,0};           //数量
int solutions = 0;                        //多少种方案

/************************************************************************ 
 * 使用面值为value[v]的钱,去凑剩下的钱remaining,remaining初始值为200
 ************************************************************************/
int Check(int v,int remaining)
{
	int i;

	//用面值 1 去凑 
	if(v == 0)             //用面值为value[0] = 1 去凑remaining
	{
		cnt[v] = remaining; //共需要remaining/cnt[v] = remaining个
		for (i=0;i<8;i++) printf("%3d",cnt[i]);//输出方案
		printf("\n");
		solutions ++;      //方案数++
		return solutions;
	}

	//不剩钱了
	else if (remaining== 0)
	{
		for(i=0;i<=v;i++) cnt[i] = 0; //小面值的都不需要了
		for (i=0;i<8;i++) printf("%3d",cnt[i]);//输出方案
		printf("\n");
		solutions ++;      //方案数++
		return solutions;
	}

	//当前面值value[v] != 1,先用 value[v]凑,剩下的递归使用value[v-1]去凑
	else
	{
		for (i=0;i<=remaining/value[v];i++)
		{
			cnt[v] = i;
			Check(v-1,remaining-i*value[v]); //递归,调用更小面值去凑
		}
	}
	return solutions;
}

int main()
{
	printf("%d\n",Check(7,200)); //从使用value[7]==200开始,去凑200
	return 0;
}

 

Python

方法1 递归求解[C\C++ 方法1 的Python版]

#coding=utf8
value = [1,2,5,10,20,50,100,200] #面值
cnt = [0,0,0,0,0,0,0,0]          #每种面值使用的数量
solutions = 0                    #方案的总数

def Check(v,remaining):
    global solutions
    if v == 0:          #使用面值1
        cnt[v] = remaining
        #print cnt
        solutions += 1
        return solutions
    elif remaining== 0: #钱已经凑齐
        for i in range(0,v):    #小面值的不需要使用了
            cnt[i] = 0
        #print cnt
        solutions += 1
        return solutions
    else:               #尝试使用value[v]去凑
        for i in range(0, int(remaining/value[v]) + 1):
            cnt[v] = i           #面值value[v]使用i个
            Check(v - 1, remaining- i * value[v] ) #用更小面值去凑剩下的钱
    return solutions

print Check(7,200) #从使用value[7]==200开始,去凑200

答案

73682

Problem 30 Digit fifth powers

Problem

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

分析

一个数等于它所有位上数字的5次方之和,找出满足这个条件的所有数的和。

肯定是需要遍历,但首先需要通过分析给出遍历的上界。

如果是一个6位数,各位数字5次方之和最大为 6 * 95 = 354294,是一个6位数,所以6位数是有可能满足的。

如果是一个7位数,各位数字5次方之和最大为 7 * 95 = 413343,是一个6位数,不可能等于7位数自身,所以7位数是有可能满足的。

这就得到了一个上界。1位数(1~9,1排除了)也是不可能的,那么就可以从10~999999遍历。

C\C++

#include <stdio.h>
#include <math.h>

/************************************************************************ 
 * 统计n的每个位的5次方之和
 ************************************************************************/
int sum_digit(int n)
{
	int sum=0;
	int digit = 0;
	while(n!=0)
	{
		digit = n%10;
		sum += (int)pow((float)digit,5);
		n /= 10;
	}

	return sum;
}

int main()
{
	int i;
	int sum = 0;
	for (i=10;i<999999;i++)
	{
		if (sum_digit(i) == i)
		{
			sum += i;
		}
	}
	printf("%d\n",sum);
	return 0;
}

Python

方法1  一行代码。 遍历10~999999,对每个数都计算各位5次方之和,如果相等,放入列表中,使用sum对列表求和。

print sum([i for i in range(10, 999999) if sum([int(ch) ** 5 for ch in str(i)]) == i])

i从10~999999遍历,对每个i,先转换为string类型,str(i),然后遍历str(i) 的每一位字符并转换为数字,再做5次方,成为列表一项,使用sum([int(ch) ** 5 for ch in str(i)]) 即可得到各位数字5次方之和,如果和i相等,则满足条件,放到外层的一个列表中,最后使用sum()函数统计满足条件的所有数之和。

答案

443839

Problem 29 Distinct powers

Problem

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a  ≤ 100 and 2 ≤ b ≤ 100?

分析

不同的幂。ab for 2 ≤ a  ≤ 100 and 2 ≤ b ≤ 100,所有的不相等的结果的个数。

思路:最大为100100 为201位,这些都可以放到一个double类型里面(double的位数大约在300位)。使用set来存储,就可以去除重复。

C++标准库中没有大数处理函数,做OJ真是一大痛啊。不过话说回来,如果都象Python一样,那么OJ也就失去了很多意义了。这也是我这个系列一直坚持,每题都用C\C++和Python两种语言解决的原因。

C\C++

方法1 double类型存储幂, STL set确保不重复

#include <iostream>
#include <set>
#include <cmath>

using namespace std;

int main()
{
	set<double> answer;
	for (double a = 2; a<=100;a++)
		for (double b = 2;b<=100;b++)
			answer.insert(pow(a,b));
	cout << answer.size();  
	return 0;
}

感谢Darryl (Project Euler 论坛 第一页)。 没想到double类型这么能装,不过总觉得这么做还是有点点侥幸,如果不是2~100,改成2~1000呢?方法就不适用了。

 

Python

方法1 一行代码,使用set存储,自动去重,使用len()统计个数

print len(set([a**b for a in range(2,101) for b in range(2,101)]))

答案

9183

知识点

  • double 类型 可以存储300位左右

Problem 28 Number spiral diagonals

Problem

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

image

It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

分析

数字螺旋对角线。求1001 x 1001的数字矩阵中,对角线数的和。 思路:通过总结规律来求和。

n x n 表示数字矩阵,diff是每一层数字之间的差距。
n = 1, diff = 0,  该层所有数为 1
n = 3, diff = 2,  该层所有数为 3,5,7,9     [3=1+2]
n = 5, diff = 4,  该层所有数为 13,17,21,25 [13=9+4]
n = 7, diff = 6,  该层所有数为 31,37,43,49 [31=25+6]
所以规律为:n层的四个数字,其差距diff=n-1

C\C++

方法1 根据规律,依次累加每一层的四个数

int n,sum=1;
int last = 1;          //前面一层的最后一个数
for(n=3;n<=1001;n+=2)
{
	//sum += last+(n-1) + last+2*(n-1) + last+3*(n-1) + last+4* (n-1);//每行四个数
	sum += 4* last +10*(n-1);
	last += 4*(n-1);
}
printf("%d\n",sum);

Python

方法1 C\C++方法1的Python版

last, sum = 1, 1
for n in range(3, 10002, 2):
    #sum += last+(n-1) + last+2*(n-1) + last+3*(n-1) + last+4* (n-1);//four number each cycle
    sum += 4 * last + 10 * (n - 1)
    last += 4 * (n - 1)
print sum

答案

666916710001

Problem 27 Quadratic primes

Problem

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² – 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

分析

二次质数。欧拉发现了著名的二次方程:n² + n + 41。当n=0~39时,这个方程能够连续产生40个质数。但是,当n=40时,402 + 40 + 41 = 40(40 + 1) + 41可以被41整除,当然,还有当n = 41, 41² + 41 + 41 可以被41整除。

发现了更奇妙的方程: n² – 79n + 1601,当n=1~79时,它能够 连续产生80个质数。方程系数的积为 –79 * 1601 = -126479.

考虑二次方程的形式:

n² + an + b,   |a| < 1000 且 |b| < 1000

|n|  是n 的绝对值。

找到系数a和b,当n从0开始连续递增时,可以产生最多的质数。给出a*b的值。

思路:一种直接的方法就是,穷举遍历。a=-1000~1000,b=-1000~1000,对每组a,b,从n=0开始往上递增,判断f = n*n+a*n+b是否是质数,如果是,则n++,cnt++,如果不是则结束,此时a,b能产生的最多质数就是cnt个。

C\C++

方法1 穷举遍历

#include <iostream>
#include <cmath>

using namespace std;

/************************************************************************ 
 * 判断n是否是质数
 ************************************************************************/
bool isPrime(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=5;i<= (int)sqrt((double)n);i++)
		{
			if (n % i == 0)
			{
				return false;
			}
		}
		return true;
	}
}

/************************************************************************ 
 * 返回n*n + a*n + b n从0开始,能连续产生的质数的个数
 ************************************************************************/
int f(int a, int b)
{
	int cnt = 0;
	for (int i=0;;i++)
	{
		if (isPrime(i*i+a*i+b))
		{
			cnt++;
		}
		else break;
	}
	return cnt;
}

int main()
{
	int max_a,max_b,max_primes=0;
	for (int a=-1000;a<1000;a++)
	{
		for(int b=-1000;b<1000;b++)
		{
			if(f(a,b)>max_primes)
			{
				max_a = a;
				max_b = b;
				max_primes = f(a,b);
			}
		}
	}
	cout<<"a="<<max_a<<" b="<<max_b<<" a*b="<<max_a*max_b<<" 连续质数个数为:"<<max_primes<<endl;
	return 0;
}

这种方法思路简单,实现起来也容易。

 

Python

方法1 穷举遍历 [相当于C\C++ 方法1 的Python版]

from math import sqrt
def isPrime(n):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    elif n % 2 == 0:
        return False
    else:
        root = int(sqrt(n))
        i = 5
        while i< root + 1:
            if n % i == 0:
                return False
            i += 1
        return True

def f(a,b):
    '''return the count of consecutive primes n*n + a*n + b can produce'''

    i, cnt = 0, 0
    while True:
        if isPrime(i*i+a*i+b):
            cnt += 1
            i += 1
        else:
            break
    return cnt

#just one line
#print max((f(a,b),a,b,a*b) for a in range(-1000,1000) for b in range(-1000,1000)) #(71, -61, 971, -59231)

#or several lines in detail
max_a, max_b, max_primes, max_product = 0, 0, 0, 0
for a in range(-1000,1000):
    for b in range(-1000,1000):
        if f(a,b) > max_primes:
            max_a, max_b, max_product, max_primes = a, b, a * b, f(a,b)
print max_a, max_b, max_product, max_prime

答案

-59231

Problem 26 Reciprocal cycles

Problem

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2=0.5

1/3= 0.(3)

1/4= 0.25

1/5= 0.2

1/6= 0.1(6)

1/7= 0.(142857)

1/8= 0.125

1/9= 0.(1)

1/10= 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d <1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

分析

一个单位分子就是分子为1。分母从2~10对应的单位分子如上表所示(即1/2,1/3,…,1/10)。

0.1(6) 表示0.16666…,拥有 1 位数字的重复周期。1/7=0.(142857) 拥有6位的重复周期。

找到d < 1000, 1/d 拥有最长重复周期的数字。

方法:模拟1/n的实际计算过程,具体的为div(n)函数。详细说明如下:

使用div(n)函数 返回 1/n 的重复周期 和 1/n的商(可选)       
模拟了实际的 1/n 的计算过程,除数始终为n,
初始状态时: 被除数numerator为1, numerator = 1,商集合fraction为空,余数集合reminder为空
执行下面的循环:
1. 如果numerator < n,不够除,则numerator *= 10,同时0追加到fraction中,如此循环,直到够除,才跳转到2   
2. 计算余数c = numerator % n,并将商numerator/n 追加都fraction中,如果c==0,则表示能除尽,不存在重复周期,返回0和fraction,跳转到4。否则跳转到3   
3. 余数c != 0, 查找reminder,确定c是否出现过,如果出现过,则出现了重复周期,则统计第一次出现(包括这次)直到reminder结束的数字个数cnt。返回cnt和fraction,跳转到4.否则将余数c追加到reminder中,c 赋给numerator,numerator = c,跳转到1,继续循环。   
4. 结束

C\C++

方法1  [思路同分析] 使用vector作为容器,使用find()函数查找

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/************************************************************************
 *功能:返回 1/n 的重复周期 和 1/n的商 (可选)   
 *说明:模拟了实际的 1/n 的计算过程,除数始终为n,被除数初始为1,numerator = 1,商集合fraction为空,余数集合reminder为空
  执行下面的循环:
  1. 如果numerator < n,不够除,则numerator *= 10,同时0追加到fraction中,如此循环,直到够除,才跳转到2
  2. 计算余数c = numerator % n,并将商numerator/n 追加都fraction中,如果c==0,则表示能除尽,不存在重复周期,返回0和fraction,跳转到4。否则跳转到3
  3. 余数c != 0, 查找reminder,确定c是否出现过,如果出现过,则出现了重复周期,则统计第一次出现(包括这次)直到reminder结束的数字个数cnt。返回cnt和fraction,跳转到4.否则将余数c追加到reminder中,c 赋给numerator,numerator = c,跳转到1,继续循环。
  4. 结束
 ************************************************************************/
int div(int n)
{
	int numerator = 1;    //被除数(分子)
	vector<int> fraction; //商 集合    (如果需要,可以返回这个商)
	vector<int> reminder; //余数 集合

	while (1)
	{
		//Step 1 : 确保numerator >= n
		while (numerator < n)
		{
			numerator *= 10;
			fraction.push_back(0);
		}

		//Step 2 :计算余数c
		int c = numerator % n;
		fraction.push_back(numerator/n);
		//cout<<"c:"<<c<<endl;
		if (c == 0)
		{
			return 0;
		}

		//Step 3 :余数不为0,判断余数是否出现过
		else
		{
			//找到c出现的位置
			vector<int>::iterator it = find(reminder.begin(),reminder.end(),c);

			if (it!=reminder.end()) //出现过
			{	
				int cnt=0;
				for (;it!=reminder.end();++it)
				{
					cnt++;
				}
				return cnt;
			}
			else //没出现过
			{
				reminder.push_back(c);
				numerator = c;
			}
		}
	}

}

int main()
{
	int max_index=0,max_cycle=0;
	for (int i=1;i<1000;i++)
	{
		if (div(i) > max_cycle)
		{
			max_index = i;
			max_cycle = div(i);
		}
	}
	cout<<"重复周期最长的数为:"<<max_index<<endl;
	cout<<"最长的重复周期为:  "<<max_cycle<<endl;
	return 0;
}

方法2  利用定理,对每个数n,重复n次 *10 并求余运算,不断往后计算余数,然后记下最后依次的余数,再不断重复*10 并求余运算运算往后找余数,如果发现新的余数与记下的余数相等了,就说明出现了重复周期。[感谢 grimbal]

void ex26(){
	int n, i, len, maxlen, maxn;
	maxlen = 0;
	for( n=2 ; n<=1000 ; n++ ){
		int rest = 1;
		int r0;

		for( i=0 ; i<n ; i++ ) rest = (rest*10)%n; // code-1

		r0 = rest;                                 //code-2
		len = 0;
		do {                                       //code-3
			rest = (rest*10)%n;
			len++;
		} while( rest!=r0 );

		if( len>maxlen ){                          //code-4
			maxn = n;
			maxlen = len;
		}
	}
	printf("ex26: %d: %d\n", maxn, maxlen);
}

通过求余数,判断余数是否会重复的思路,和方法1是相同的。但是grimbal大神 code-1 行,为什么要使用n,而不是其它数字呢, grimbal的代码没有任何解释,只能自己思考。

rest = (rest*10)%n 的意思就是不断往后找余数,循环n次后,rest就是第n个余数的值。然后code-2处记录下了这个值到r0中。code-3的循环与code-1相似,很好理解,就是继续往后找余数,只要发现新找的余数rest和r0相等了,就说明余数重复出现了,也就是出现重复周期。len就记下了两次重复之间的数字个数,即重复周期的大小。

code-4 处用来记录下重复周期最大的数。

问题的关键还是在于:code-1为什么用的是n? 用n的意思就是1/n的余数最多n次就必然会出现循环?这有何根据?

通过搜索,我找到到了如下的定理:

定理:任意自然数N,在1/N后,得到有限小数或者是无限循环小数且循环字节数小于N-1

看来数学理论对于解题确实太有帮助了!

代码来自:ProjectEuler 论坛 第 1 页,第 2 贴。

Python

方法1 [思路同分析] 基本上类似于C\C++方法1

#coding=utf-8

#返回 1/n 的重复周期 和商
#模拟了实际的 1/n 的计算过程,记录余数,当余数出现重复时,说明出现了循环,两次重复之间的数字个数就是重复周期
def div(n):
    #if n % 10 == 0:   #10的倍数肯定都能除尽,如果不需要具体的商,可以在此处提前返回
    #    return 0
    numerator = 1       #分子
    fraction = []       #存放小数部分数字 (可以用来获得具有循环周期的数的具体的小数部分)
    reminder= [1,]      #存放所有的余数用来,判断是否出现了循环,第一个肯定是1
    while True:
        #(保证numerator >= n 分子大于分母)
        while numerator < n:
            numerator *= 10
            fraction.append(0)  #0放到fraction中
        c = numerator % n       #分子除以分母的余数
        fraction.append(int(numerator / n)) #商放到fraction中
        if c == 0:              #可以除尽,则重复周期为0
            return 0, fraction #返回重复周期0,商

        #不可以除尽,判断余数c 是否出现过,如果出现过,说明出现了循环。否则放到reminder中
        if c in reminder:
            #找到c和前一个c 之间数的个数
            cnt, flag = 0, False
            for i in reminder:
                if i == c:
                    flag = True
                if flag == True:
                    cnt += 1
            return cnt, fraction
        else:
            reminder.append(c)
            numerator = c     #余数作为分子,继续除

#重复周期最大的数,最大的重复周期,最大的数对应的商
max_index, max_cycle, fraction = 1, 0, []
for i in range(2,1000):
    if div(i)[0] > max_cycle:
        max_index, max_cycle, fraction= i, div(i)[0], div(i)[1][:]
print max_index, max_cycle,fraction

答案

983

知识点

  • 定理:任意自然数N,在1/N后,得到有限小数或者是无限循环小数且循环字节数小于N-1

Problem 25 1000-digit Fibonacci number

Problem

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

分析

求Fibonacci数列的第一个包含1000位数字的项对应的序号。依旧是一个大数问题。使用之前解题过程中写的大数处理函数(Problem 20, mul函数中有两个大数的加法)可以解决该问题。

方法:C\C++ 编写函数big_add(char* a, char* b)实现两个大数的加法;Python中处理大数毫无压力,对待大数的题目,使用Python就象作弊的感觉。

C\C++

方法1 用字符串存放大数。编写big_add(char* a, char* b)实现两个大数的加法。

big_add()函数如下

/************************************************************************
 * 功能:两个大数的加法
 * 说明:a和b是两个大数,保存在字符串,如1234+789,a="1234",b="789"
 * 返回:a+b和的字符串的指针,big_add函数内部已分配空间。
 ************************************************************************/
char* big_add(char* a, char *b)
{
	char* p1 = NULL;  //指向较长的字符串
	char* p2 = NULL;  //指向较短的字符串
	char* sum = NULL; //指向和
	int len1 = 0;     //较长字符串的长度
	int len2 = 0;     //较短字符串的长度
	int acc = 0;      //加法过程中的进位
	int i,j,k,v,v1,v2;
	char* tmp = NULL;

	if(strlen(a)>=strlen(b))
	{
		p1 = a;
		p2 = b;
		len1 = strlen(a);
		len2 = strlen(b);
	}
	else
	{
		p1 = b;
		p2 = a;
		len1 = strlen(b);
		len2 = strlen(a);
	}

	//和sum
	sum = (char*)malloc(sizeof(char)*(len1+1)); //初始和较长的字符串等长。+1: \0

	//sum = p1
	for (i=0;i<=len1;i++)
	{
		sum[i] = p1[i];
	}

	//sum += p2

	//sum和p2低位相对应的位相加

	acc=0; //初始化低位的进位为0
	for(i=len1-1,j=len2-1;i>=0&&j>=0;i--,j--)//i是sum的位,j是p2的位,从字符串的高位往低位,即从数字的低位往高位
	{
		v1 = (int)(sum[i]-'0');
		v2 = (int)(p2[j]-'0');
		v = v1+v2+acc;
		acc = v/10;
		sum[i] = (char)((v%10)+'0'); //模10的结果作为和sum[i]
	}

	//由于len1>=len2,所以跳出循环时,j == -1
	//如果此时,acc=0,即无进位,sum就是最后的和,结束
	//如果此时,acc!=0,即有进位,sum还需要加上acc

	//有进位
	if (acc!=0)
	{
		//i==-1,表明sum和p2同时遍历完了,两者等长,此时sum需要多加一位,存放进位acc
		if(i==-1)
		{
			tmp = (char*)malloc(sizeof(char)*(len1+2));//加:一位空白和一位\0
			for(k=0;k<=len1;k++) //tmp[1...len1] = sum[0,len-1]
			{
				tmp[k+1] = sum[k];
			}
			tmp[0] = acc+'0';               //最高位

			delete[] sum;
			sum = tmp;
		}

		//sum 还没有遍历完,此时需要对sum+=acc
		else
		{
			//此时,i指向sum将要计算的位置
			for (;i>=0;i--) //对sum继续 + 进位
			{
				v1 = sum[i]-'0';
				v = v1+acc;
				sum[i] = (v%10)+'0'; //模10的结果
				acc = v/10;          //进位

				if(acc ==0 )break;   //没有进位了,停止
			}

			//跳出循环时,要么acc==0 要么i==-1
			//若是acc=0,则sum就是最后的和
			//若是i==-1, 说明不是break跳出的,此时acc!=0,还有进位

			if(i == -1)  //进位
			{
				tmp = (char*)malloc(sizeof(char)*(len1+2));//加:一位空白和一位\0
				for(k=0;k<=len1;k++) //tmp[1...len1] = sum[0,len-1]
				{
					tmp[k+1] = sum[k];
				}
				tmp[0] = acc+'0';               //最高位

				delete[] sum;
				sum = tmp;
			}
		}
	}
	return sum;
}

有了big_add()这个利器之后,计算Fibonicci就变得很简单了。

char* a = NULL;
char* b = NULL;
char* c =NULL;
int term=2;

a = (char*)malloc(sizeof(char)*2); //使用malloc是为了后面的delete一致
b = (char*)malloc(sizeof(char)*2);
a[0] = '1';a[1]='\0';
b[0] = '1';b[1]='\0';

while (1)
{
	c = big_add(a,b);
	term ++;
	if(strlen(c) == 1000)
	{
		printf("%d %s\n",term,c);//输出结果
		delete[] c;
		break;
	}
	delete[] a;

	a = b;
	b = c;
}

Python

方法1 直接法

f1, f2, term = 1, 1, 2
while True:
    f3 = f1 + f2
    term += 1
    if len(str(f3)) >= 1000:
        print term, f3
        break
    f1, f2 = f2, f3

答案

4782

知识点

  • C\C++  大数的加法实现(big_add函数)

华为机试感悟

前天接到通知,今天下午去滨江参加机试,1点钟开始,到滨江还早,却赶了很长一段路才压着点到了华为的机房。机房倒挺干净明朗的,里面整齐的一排排显示器,机器性能也还过的去,至少我用的那台还不错。机子只装了一个VC6.0,虽然这是事先已经知道的,但仍觉得使用过程会不习惯,一则已经很久不用VC了,追求轻便时就用CodeBlocks,想要调试功能强大时,就用VS2010,二则自己常用的IDE,不但本身提示功能齐全,而且我还装了VA,敲起代码感觉如鱼得水,轻快愉悦啊。不过,坦诚的说,一个不卡的机器,一个还算熟悉和强大的编译器,能提供这些,就很好很满足了,但是后面的编码过程,自己敲的确很happy,不间断的啪啪响,一边敲一边想接下来的,不用停下来选择提示框的选项,看来没有提示,或许也是一种快感吧。

机考之前是长长的,长的不能再长的,冗长的心理测试问卷。足足36部分,每部分通常还分两、三页,每页上还是许多道的问题,每题还有强烈不同意…比较不同意…强烈同意等不同选项,真是很需要耐心啊。据说心理测试也会刷人,只得每题都看完想好再填,还在集中精力时,本人的效率还是挺高的。也算是率先完成了问卷,进入了测试题目吧。

考题是三道,我看了一眼题目后,就依次从第1题开始做,这个系统之前让我们体验过,所以用起来还顺手。第一题是密码,设a~z 为数字1~26,A~Z为27~52,给定一个字母,获取其数字x, f = x*x +x +1,f 为加密后的字符的数字,如果超过52,则取52的模,f转换为相应的字符,就是加密后的字符。问题输入是一个字符串,要求输出是这串字母的加密后的字符串。问题很简单,就象是C语言教材后面的练习题,简单的转换就可以了。

第二题也是类似C语言教材后面的练习题,简单的字符统计即可。题目是这样的,要求判断一个密码是否符合条件:1. 8~20个字符,2,只能是数字,字母,和给定的一些特殊字符(请允许我记不全了),3. 数字,小写字母,大写字母,特殊字符,必须至少包含以上四种中的三种。问题输入是若干行密码,要求输出是true(符合)或false(不符合)。依次遍历一遍密码即可。

前两题做的很快,几乎是看完题目就敲代码,一边敲一边想。

进入第三题,问题有些复杂,叫好友管理。给了一大堆变量,还有什么好友推荐。最后结合测试样例才看懂的,也就那么回事,虽然说的那么复杂(我觉得题目中表述还可以再改进改进)。简单的说,就是给定一个人名,再给定几组人名,每组人名包括两个人名,这两个人就是好友,好友是相互的。好友推荐呢,就是,如果两个人不是好友,但是有超过p个共同好友,就推荐为好友(写到这,我发现我当时是不是理解的有问题,把这个好友推荐没弄清楚,到底这么个推荐规则,我当时好像是把两个人的所有好友都互加为好友了,唉,原来如此,醒悟的太晚了,给我弄复杂了)。我就用一个class User{} 来代表一个用户,他有AddFriend(),FrientCnt()等函数,内部使用一个vector容器保存他所有的好友。这样就很方便管理了。代码写了一会,行数有点多,测试了一下样例,可以跑通,就匆匆提交了。刷新后却是答案错误,错误信息就是判题系统的测试样例没有跑通。有点纳闷啊。代码写的匆匆貌似也不很好调试,况且要我我写一个测试样例又太麻烦了,改过几次,都没有通过。有点懊恼啊。感觉这题目不难啊,但是通不过,还不知道错在哪,郁闷啊。

反正就这样了,还是讲讲感悟吧。

平时多做些OJ或者其它类似的判断系统还是很有好处的,遇到题目时,思路会清晰。这段时间我就在搞ProjectEuler,每到题目我都希望用更多中方法去解决,用C\C++和Python两种语言去解决。做的多了,机试就像平时做题一样,投入进去了,就慢慢忘了周围的一切,不会有那么紧张。(虽然最后我还是感觉有点急躁,不过整场考完还是心情保持的很好,毕竟这也是第一次机考嘛)

使用C++会比C更高效。我不是说的运行速度,我是说的解题速度。之前我还经常会使用C,但是一到机试,发现明显使用C++会顺手的多,至少变量定义一块,就舒服很多。还有一点,就是使用STL中的容器和算法,会免去很多不必要的代码,也就减少了出错率。对于动态大小的数组,我都是使用vector去替代,不用自己考虑内存分配什么的问题,很方便。今天三题都是用的C++,很顺手吧还是。虽然之前还在C和C++之间犹豫,舍不得C的一些东西,尤其什么printf之类的格式化输出。

不知道接下来是什么结果,慢慢等吧。

Problem 24 Lexicographic permutations

Problem

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

分析

将数字0-9 按照字典顺序排列,求第1,000,000个排列

方法:0-9的全排列有10! = 3,628,800种。不可能把所有的排列都遍历一边找第1,000,000个。但是由于是按字典顺序的,所以可以从0位开始往后找。

每个数放在第0位,后面都有9!种排列。每个数放在第1位,后面都有8!种排列。后面的同理。

第0位 是数字 0,第一个排列是0123456789,即整体的第1个排列。

第0位 是数字 1,第一个排列是1023456789,即整体的第 9! + 1 个排列。后面的同理。

所以,若第一位数字是n,则n要满足n的第一个排列比1,000,000 小,n+1的第一个排列比1,000,000大。即 n*9!+1 <1,000,000 && (n+1)*9! + 1 >1,000,000。

第0位数字p0确定后,再确定第1位的数字p1。

p0打头的第一个排列的次序是 p0 * 9! +1。所以第1,000,000个数,也就是p1开头的第less = 1,000,000 –  (p0 * 9! +1) 个数。

此时相当于 从0~9(除去p0)中挑选出第n个数,满足

n*8!+1 <less && (n+1)*8! +1 >less.

依次类推,确定获得每一位。

总结下规律: less=1,000,000,确定第 i 位的数字时,求n,满足n*(9-i)! + 1 <less && (n+1)*(9-i)! + 1 >less,然后从0~9中按顺序找到第n个数字,作为第 i 位的数字,然后,less –= n*(9-i)! + 1。i++,再同理确定下一位。

还有个更简单,但是看起来比较蠢的办法,就是从00000 00000 到 99999 99999 遍历一遍,只要每一位都不相等,那么cnt++,当cnt==1,000,000时,输出此时的数字。伪代码如下

for(bit0=0;bit0<=9;bit0++){
	for(bit1=0;bit1<=9;bit1++){
	   ...
		for(bit9=0;bit9<=9;bit9++){
			//如果bit0 ... bit9都不相同
			cnt ++; //cnt初始为0
			if(cnt== 1000000) printf bit0,bit1,...bit9
		}
	}

}

当然只要0不在首位,也可以省略这么多层for循环,从1023456789开始,这是第9!+1 个数列,到9876543210遍历,每当各位都不相同,cnt++,当cnt==1,000,000时,输出数字即可。代码为C\C++ 方法3

C\C++

方法1 [原理同分析]  使用perm[10]来表示第1,000,000个排列,使用flag[10] 来表示0~9是否已用。

#include <iostream>

using namespace std;

const int limit = 1000000;
int perm[10];    //存放最终的排列
int flag[10];    //标志0-9是否已使用

/*返回n!*/
int A(int n)
{
	int rel=1;
	for(int i=1;i<=n;i++)
		rel *= i;
	return rel;
}

/*设定数列的每一位*/
void set_bit(int less) //less 表示 里1000000还差多少
{
	//10次循环,每次确定perm[]的一位数字
	for (int n=0;n<10;n++)
	{
		int i,k,cnt;
		int a = A(9-n);

		//第n位数字的次序
		for(i=0;i<=9;i++)
		{
			if ( i*a + 1 <=less && (i+1)*a +1 >less )
			{
				cout<<"n="<<n<<" i="<<i<<", "<<i*a + 1<<" "<<less<<" "<<(i+1)*a +1;
				less -= i*a;
				break;
			}
		}

		//从flag数组中,选出第no个没有用的数字
		cnt=0;
		for(k=0;k<10;k++)
		{
			if(flag[k] == 0) cnt++;
			if(cnt==i+1)
			{
				perm[n] = k;
				flag[k] = 1;
				cout<<" "<<k<<endl;
				break;
			}
		}
	}
}

int main(int argc, _TCHAR* argv[])
{
	int i;
	for (i=0;i<10;i++) flag[i]=0; //初始化所有数字都未使用

	set_bit(limit);                //获取每一位

	for (i=0;i<10;i++)
	{
		cout<<perm[i];
	}
	cout<<endl;
	return 0;
}

 方法2 使用STL中algorithm算法库中的next_permutation()函数  [感谢 cd-rw]

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    char ca[]="0123456789";

    for(int i=1;i<1000000;i++)
        next_permutation(ca,ca+10); 
    cout << ca << endl;
    return 0;
}

next_permutation() 产生序列字典序的下一项

来自 Project Euler论坛 第 1 页

方法3 [简单粗暴]从1023456789开始,到9876543210遍历,每当各位都不相同,cnt++,当cnt==1,000,000时,输出数字

#include <stdio.h>

/*如果整型的每一位数字都不相同,返回1,否则返回0*/
int every_bit_diff(int n)
{
	int i,j;
	int digit[10];      //保存i的每一位数字
	for (i=0;i<10;i++)
	{
		digit[9-i] = n%10;
		n /= 10;
	}

	int flag = 1;
	for (i=0;i<9;i++)
	{
		for(j=i+1;j<10;j++)
		{
			//只要有两位数字相等,返回0
			if (digit[i] == digit[j]){flag = 0;	}
		}
	}
	return flag;
}

int main()
{
	int cnt = 362880;//9! 0开头的所有排列总数
	for(int i=1023456789;i<=9876543210;i++)
	{
		if (every_bit_diff(i)) //i的每一位数字都不相同
		{
			cnt++;
			//printf("%d,cnt=%d\n",i,cnt);
		}
		if (cnt == 1000000)
		{
			printf("%d\n",i);
		}

	}
	return 0;
}

算法简单,但运行时间久。

Python

方法 1 [原理同C\C++方法1] 使用列表存储,方便将已用的数字删除。

def A(n):
    '''return n!'''
    if n == 0 or n == 1:
        return 1
    else:
        return reduce(lambda x,y:x*y,range(1,n+1))

perm = []
digits = list('0123456789')

limit = 1000000
for i in range(0,10):
    for n in range(0,10):
        if n * A(9-i) + 1 <= limit and (n + 1) * A(9-i) +1 > limit:
            perm.append(digits[n])
            digits.remove(digits[n])
            limit -= n*A(9-i)
            break
print perm

A(n) 返回n!。 0~9 按序存储在列表digits中。如果对于排列的第i位(从0开始) n * A(9-i) + 1 <= limit and (n + 1) * A(9-i) +1 > limit。表明第i位的数字是digit[n],所以perm[i] = digit[n],然后将digit[n]从digit[] 列表中删除,limit –= n * A(9-i) + 1 。

答案

2783915460

知识点