这下我们可以开始我们的Haskell之旅了，我们说过Haskell有两种执行的环境，一种是动态脚本语言那种输入即得结果的方式，另一种是编译执行方式。我们闲来进行第一种，与python类似，Haskell也有个相似的环境，我的环境是Fedora 11下GHC 6.10.3，大家要安装的话直接yum即可。我们输入ghci后即可进入我们需要的环境了，显示效果如下：

最近看到了这个网站：learnyouahaskell.com/，相当于一个Haskell教程，内容很不错，插图很有意思，学习起来很快，因此最近就开始看这个资料，并留下一些学习笔记供以后回来复习之用。不得不说网上关于Haskell的资料不算太多（和C/C++那些比），但是好资料也不少，如《Real World Haskell》，《Programming in Haskell》还有《Yet Another Haskell Tutorial》等等，但是有些时候学习起来会有一定的难度，各个教材侧重点也都不同，之前也都大概浏览了一下，有了个大概的认识，现在就来看看这篇文章写得如何了，基本上的原则是看一章后写个总结，慢慢看，深入理解。

前段时间参加了一场比赛，有个题目令我印象深刻，但是当时太忙，没时间记录下来，最近比较有空就暂做记录。

问题来自USACO CONTEST Elite 2009 November Competition这场比赛的golden组的名为lights的题目。

前言

前言只有一个内容：我很爱国。还有一点，分割线以下的内容作用于仅限于分割线以下，谢谢合作。

=================华丽的分割线=================

分割线以下的内容全部都是瞎扯淡，没有一句是真的。

看懂上面逻辑的可以继续往下了……

原题与答案：

Problem 35

17 January 2003

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?

Answer:55

分析与解答：

这个题目是求1000000以内所有循环本身都是素数的数的个数，比如197循环本身就有197,971和719三个。这个题目最早的时候想要优化一下，避免重复求解，即既然循环一圈都是素数，那么求过的就一起在最小的那个算掉，不用重复求解了。但是这样计算有一个问题，算出的结果都是56，错误就在于11这个数，11自循环后就是本身，这里重复累计了一次，后来用最为朴素的算法得出了55才发现错在哪里，朴素的算法就是一个个素数去枚举，然后累加和，程序非常简单，关键就在打素数表，具体的实现源程序代码如下：

#include<stdio.h>
#include<string.h>
bool nprime[1000001];
int i,j,a[80000],ans;
int check(int s)
{
int i,j,k,cnt=0;
for (i=1,j=10;s>=j;i++,j*=10);
for (j/=10,k=1;k<i;k++)
{
s=(s%j)*10+s/j;
if (!nprime[s])
cnt++;
}
return cnt==i-1;
}
int main()
{
a[0]=0;
memset(nprime,false,sizeof(nprime));
for (i=2;i<=1000000;i++)
if (!nprime[i])
{
a[++a[0]]=i;
if (i<=1000)
for (j=i*i;j<=1000000;j+=i)
nprime[j]=true;
}
ans=0;
for (i=1;i<=a[0];i++)
if (check(a[i]))
ans++;
printf("%d\n",ans);
return 0;
}

原题与答案：

Problem 34

03 January 2003

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.

Answer:40730

分析与解答：

这个题目是求除了1和2以外的等于自身各位数值阶乘的和的数，输出他们的和。题目本身的难点在于求范围，因为如果我们需要枚举的数值范围很大的话就要考虑用构造的方法了，所以我们先来判定一下一个n位数他的求值范围是 $n \leq s \leq n*9!$ ，那么我们可以很容易想到那个n位数不可能是无限大的，因为每加上一位，和最大只添加9!=362880，于是通过尝试发现n为8的时候，求值范围是 $8 \leq s \leq 2903040$ ，在最大值只有7位数，明显8位数不在我们的枚举范围之内。同时n为7的时候 $7 \leq s \leq 2540160$ ，还可能存在所求的数值，因此我们枚举的范围最后定下来是 $10 \leq s \leq 2540160$ ，自然就得到了如下程序源代码了：

#include<stdio.h>
int fact[10],base[10],i,j,s,ans;
int calc(int s)
{
int ret=0;
while (s)
{
ret+=fact[s%10];
s/=10;
}
return ret;
}
int main()
{
fact[0]=1;
for (i=1;i<=9;i++) fact[i]=fact[i-1]*i;
base[0]=1;
for (i=1;i<=7;i++) base[i]=base[i-1]*10;
for (s=fact[9],i=2;i<=7;i++)
{
s+=fact[9];
for (j=base[i-1];j<base[i]&&j<=s;j++)
if (calc(j)==j) ans+=j;
}
printf("%d\n",ans);
return 0;
}

原题与答案：

Problem 33

20 December 2002

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ³⁰/₅₀ = ³/₅, 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.

Answer:100

分析与解答：

这个题目是说形如 $\dfrac{ab}{bc}=\dfrac{a}{c}$ 的小于1的分数一共有四个，其中ab和bc均为两位数，问这四个分数的乘积的最简分式的分母是什么。这个题目很明显是一个枚举题，这里要用到的就是一个最大公约数的过程，求最大公约数我们可以利用辗转相除法来实现，然后分别依次枚举b,a和c，要注意的是三个数都必须非0，而且c>a，实际上这题的实现很简单，具体的程序源代码如下所示：

#include<stdio.h>
int i,j,k,s,t,num,den;
int gcd(int x,int y)
{
int t;
while (t=x%y)
{
x=y;
y=t;
}
return y;
}
int main()
{
num=den=1;
for (i=1;i<10;i++)
for (j=1;j<10;j++)
for (k=j+1;k<10;k++)
{
s=gcd(j*10+i,i*10+k);
t=gcd(j,k);
if ((j*10+i)/s==j/t&&(i*10+k)/s==k/t)
{
num*=j;
den*=k;
}
}
printf("%d\n",den/gcd(num,den));
return 0;
}

原题与答案：

Problem 32

06 December 2002

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 × 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.

Answer:45228

分析与解答：

这个题目是求所有的满足条件的乘法表达式的积的和，题目中的条件是要求表达式中出现1到9这9个数字，每个有且只有一次。仔细分析一下去掉一些不可能的情况，首先是我们的表达式里面一共有9个数字，这样我们先考虑生成9的全排列，然后再加入乘号和等号，同时考虑到我们加入乘号和等号的情况总数为C(8,2)=28种，我们可以从这里排除掉一大堆不可能的情况。对于一个n位数和一个m位数的乘法，他们的积只可能是n+m或者是n+m-1位数，于是乎我们可以假设当被乘数小等于乘数的时候，我们得到的只可能有两种情况符合题意，即1位数*4位数=4位数或者是2位数*3位数=4位数，这样我们就将情况数从28种缩减到了2种，然后就是枚举计算的事情了，实际上满足条件的表达式非常少，因为积都是4位数，不会超过P(9,4)=3024个，但是实际算出来只有9个。我的程序源代码如下所示：

#include<stdio.h>
#include<string.h>
#include<algorithm>
int list[10],prod[3100],i,j,ans,s,t,u;
bool yet[10],first=true;
void check()
{
int i;
for (u=0,i=5;i<9;i++) u=u*10+list[i];
for (s=i=0;i<1;i++) s=s*10+list[i];
for (t=0,i=1;i<5;i++) t=t*10+list[i];
if (s&&t>=1000&&u>=1000&&s*t==u)
prod[++prod[0]]=u;
for (s=i=0;i<2;i++) s=s*10+list[i];
for (t=0,i=2;i<5;i++) t=t*10+list[i];
if (s>=10&&t>=100&&u>=1000&&s*t==u)
prod[++prod[0]]=u;
}
void calc(int pos)
{
if (pos==9) check();
else
for (list[pos]=1;list[pos]<=9;list[pos]++)
if (!yet[list[pos]])
{
yet[list[pos]]=true;
calc(pos+1);
yet[list[pos]]=false;
}
}
int main()
{
prod[0]=0;
memset(yet,false,sizeof(yet));
calc(0);
std::sort(prod+1,prod+prod[0]+1);
for (ans=0,i=j=1;;i=j)
{
ans+=prod[i];
while (j<=prod[0]&&prod[i]==prod[j])
j++;
if (j>prod[0]) break;
}
printf("%d\n",ans);
return 0;
}

原题与答案

Problem 31

22 November 2002

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:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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

Answer:73682

分析与解答：

题目是说给定八种币值：1,2,5,10,20,50,100,200，问组成200一共有多少种可能。这是一个很经典的找钱问题，当然当钱币数量不多的时候可以搜索，直接枚举找到答案，但是有一种更好的方法，那就是利用动态规划来求解，首先我们得到动态规划方程： $\begin{displaymath}F[i][j]=\sum_{a[k]\leq j}{F[i-1][j-a[k]]}\end{displaymath}$ 。其中F[i][j]表示用前i种币值拼出j有多少种，那么就很容易可以理解那个方程了。当然我们注意到，新的F[i]总是依赖于F[i-1]的，因此我们可以从这个方面来考虑缩减空间消耗，可以利用滚动数组来实现，这样我们的空间消耗就是2*n了，同时我们看到由于对于j的值总是利用比j小的值求得，因此我们可以换一种思路，利用j求j后面的值，这样就又一次减少空间为一个一维数组了，初始化的时候我们设置得到0这个值有1种方法，具体的实现见程序源代码：

#include<stdio.h>
#include<string.h>
int coins[8]={1,2,5,10,20,50,100,200},cnt[201],i,j;
int main()
{
memset(cnt,0,sizeof(cnt));
cnt[0]=1;
for (i=0;i<8;i++)
for (j=0;coins[i]+j<=200;j++)
cnt[j+coins[i]]+=cnt[j];
printf("%d\n",cnt[200]);
return 0;
}

原题与答案：

Problem 30

08 November 2002

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

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ 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.

Answer:443839

分析与解答：

这个题目的意思是找出所有的等于自己各个位数五次方的和的数（除了1），输出他们的和。题目书写起来很简单，关键难点在于数值范围的判断，因为首先我们的直观想法：如果我们不停的加0，那么数值可以不断变大，但是五次方和不变，同时如果我们加上其他数值，可以调节两者大小关系，貌似这个枚举量是无穷的，但是仔细分析下来，我们得到结论是这个数最多就6位，下面先列出一个表格：

N	0	1	2	3	4	5	6	7	8	9
	0	1	32	243	1024	3125	7776	16807	32768	59049
0	1	0	-31	-242	-1023	-3124	-7775	-16806	-32767	-59048
1	10	9	-22	-233	-1014	-3115	-7766	-16797	-32758	-59039
2	100	99	68	-143	-924	-3025	-7676	-16707	-32668	-58949
3	1000	999	968	757	-24	-2125	-6776	-15807	-31768	-58049
4	10000	9999	9968	9757	8976	6875	2224	-6807	-22768	-49049
5	100000	99999	99968	99757	98976	96875	92224	83193	67232	40951
6	1000000	999999	999968	999757	998976	996875	992224	983193	967232	940951

首先上面的表格第二行表示 N^5 ，然后下面每行都表示 10^i-N^5 ，换句话说表示的是将数字j固定在i位会对原数减去本位的五次方造成多大的差值。我们的最终结果是在每行取且只取一列使得这些数值的和是0，那么我们如果要让原来数值尽量大，换句话说，如果我们要让数值的位数尽量多，我们就要取负值绝对值较大的，正值绝对值较小的。我们从表中得到我们从低位开始依次要取的数值是9，9，9，9，9，9，9，也就是说当取到6位的时候，不管怎么取，值都是正数，我们先把前5位取9，此时的数值是 -59048-59039-58949-58049-48049+10951=-272183 ，这样就算我们最高位取值是0都会为正数，当然我们最高位不能取0，就取1吧，但不管怎么说，这个数值始终是保持在6位，不可能再大了，因此我们得到了范围后就可以放心枚举了，注意的一点是，最后的结果要把1去掉，我的程序源代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
int ft[10]={0,1,32,243,1024,3125,7776,16807,32768,59049},s,ans,a[6],b[6];
bool get(int s)
{
int i;
for (i=0;i<6;i++)
{
b[i]=s%10;
s/=10;
}
std::sort(b,b+6);
return !memcmp(a,b,sizeof(a));
}
int main()
{
ans=0;
for (a[0]=0;a[0]<=9;a[0]++)
for (a[1]=a[0];a[1]<=9;a[1]++)
for (a[2]=a[1];a[2]<=9;a[2]++)
for (a[3]=a[2];a[3]<=9;a[3]++)
for (a[4]=a[3];a[4]<=9;a[4]++)
for (a[5]=a[4];a[5]<=9;a[5]++)
{
s=ft[a[0]]+ft[a[1]]+ft[a[2]]+ft[a[3]]+ft[a[4]]+ft[a[5]];
if (get(s)) ans+=s;
}
printf("%d\n",ans-1);
return 0;
}

Learn You a Haskell for Great Good!——(2)起步

Learn You a Haskell for Great Good!——(1)Haskell简介

二进制状态转移的最小覆盖问题

满嘴顺口溜，你想考研啊

前言

Project Euler——Problem 35

原题与答案：

Problem 35

分析与解答：

Project Euler——Problem 34

原题与答案：

Problem 34

分析与解答：

Project Euler——Problem 33

原题与答案：

Problem 33

分析与解答：

Project Euler——Problem 32

原题与答案：

Problem 32

分析与解答：

Project Euler——Problem 31

原题与答案

Problem 31

分析与解答：

Project Euler——Problem 30

原题与答案：

Problem 30

分析与解答：