一点一点前进...

0%

操作系统(Operating System, OS)复杂确保系统易于使用且正确高效地运行。
操作系统主要利用虚拟化(virtualization)的技术,将物理资源(如处理器、内存、磁盘等)变得更通用、更强大、更易于使用,所以有时也将操作系统成为虚拟机(virtual machine)。
操作系统也提供很多接口(API) - 系统调用(system call) -让程序调用来访运行程序、访问内存和设备,进行其他操作等,换句话说,操作系统为应用程序提供了一个标准库(standard library)。
由于共享,操作系统需要管理(manage)这些系统的资源(resource),如CPU、内存、磁盘等,所以操作系统也是一个资源管理器(resource manager)。

虚拟化CPU

操作系统在硬件的帮助下,将单个CPU转化成了看似无限多的CPU,从而让多个应用程序同时运行,这就是虚拟化CPU(virtualizing the CPU)。
多个程序同时运行会导致新的问题,最简单的要在合适运行具体哪个程序。这个由操作系统的策略来决定。

虚拟化内存

每个运行的程序都有自己的私有内存,而不是于其他运行的程序共享相同的物理内存,这就是虚拟化内存(virtualizing memory)。每个进程访问自己的私有虚拟地址空间(virtual address space),或地址空间(address space),操作系统以某种方式映射到物理内存上。一个运行的程序中的内存引用不会影响到其他程序(包括操作系统自身)的地址空间。

并发

多个程序同时运行会产生并发(concurrency)问题,其不再局限于操作系统,现代多线程程序也有同样的问题。

持久性

持久性(persistence),利用硬件和软件来持久地(persistently)存储数据。
硬件以某种输入/输出(Input/Output, IO)设备的形式出现,比如硬盘驱动器(hard drive)、固态硬盘(Solid-State Drive, SSD)。
操作系统中管理磁盘的软件通常称为文件系统(file system),可靠高效地将用户创建的任何文件存储在系统的磁盘上。
操作系统不会为每个应用创建专门的虚拟磁盘。

其实iOS某种意义上就是为应用程序创建了磁盘,或者说一个专有目录。

设计目标

建立抽象(abstraction),让系统方便和易于使用。
高性能,目标就是要最小化操作系统的开销(minimize the overhead)。虚拟化和易于使用是非常值得的事情,但是不会不计成本。完美的设计并不总是存在,必要时要做出权衡。
另一个目标是在程序之间以及OS和程序之间提供保护(protection)。确保不会一个不当程序影响其他程序,更不会影响操作系统本身。保护的核心原理是隔离(isolation)。
可靠性(reliability)。
其他目标还有能源效率(energy efficiency)、安全性(security)、移动性(mobility)等。
根据系统的使用方式,将有不同的目标,可能会以不同的方式实现。

Problem 86

小蚂蚁从立方体的一点走最短距离爬到对顶点,爬过的长度可能是整数,比如立方体三维分别是6,5,3,那么最短距离是10,但也不总是整数。
对于三边最长是$M\times M\times M$的立方体,当$M=100$时,有2060个边长均为整数的不一样的立方体,其蚂蚁爬过的最短距离是整数,而$M=99$时,有1975个不同的立方体。
求立方体个数超过一百万时$M$的最小值。

其实这个题目不难,关键点在于不需要计算出具体满足题意的值,只需要计数即可。
不妨设$M=a\geq b\geq c$,那么$2\leq b+c\leq 2a$,斜边长是$\sqrt{a^a+(b+c)^2}$,如果斜边长是整数,那么$b$和$c$可以在一定范围内变化。$b$最小也就是$b+c$的一半或者一半加一,最长的话就是等于$a$,同时要满足$c\geq 1$。所以很容易通过某个给定的$a$来得到满足条件的个数。

阅读全文 »

700题链接

先瞎扯一句,欧拉项目网站的第700题(整百哦)有纪念欧拉意味,看得出来,出题人很有情怀。

欧拉(Leonhard Euler)出生于1707年4月15日。
考虑序列$1504170715041707n \mod 4503599627370517$。
在这个序列的元素,如果小于前一个Eulercoin,那么它就是Eulercoin。
显然第一个Eulercoin是1504170715041707,也是序列的第一个数;该序列的第二个数3008341430083414比上一个Eulercoin大,它不是Eulercoin,第三项8912517754604比第一项小,所以是新的Eulercoin。
求所有Eulercoin之和。

阅读全文 »

原题链接

$2^7=128$是第一个以12开头的2的幂次数。下一个是$2^{80}$。
$p(L,n)$表示满足$2^j$以$L$开头的第$n$个$j$的值。所以$p(12,1)=7$,$p(12,2)=80$。
题中给出$p(123,45)=12710$以验证程序。
求$p(123,678910)$。

$2^{12710}$就是一个比较大的数字,如果使用BigInteger.ToString检查其是否以123开头还好,但是这才第45个以123开头的幂次,第678910个满足条件的幂次要大的多得多,时间也要长太多,所以我们需要一个速度更快的方式来检查。

阅读全文 »

题目链接

$s(n)$的定义是数字之和是$n$的最小值,比如$s(10)=19$。
$S(k)=\sum_{n=1}^ks(n)$,题中给出$S(20)=1074$,可以用于检测程序是否基本正确。
$f_i$是斐波那契数列。
问题是求$\sum_{i=2}^{90}S(f_i)$模1000000007。

斐波那契数列以指数速度增长,所以暴力法肯定是不行的($f_{90}$快接近long的表示上限了),那么需要在常数或者对数时间复杂度的算出$S(k)$的算法。
$s(n)$其实很容易想,数字最小,那么就是高位的值越小越好,那么低位的值都是9即可。
有了$s(n)$,我们就可以推导一下$S(k)$了。

阅读全文 »

100题链接

正整数方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$。如果$n=1260$,那么有113个不同的解,这个解的数量超过100的最小的$n$值。
求不通解的数量超过4百万的$n$的最小值。

$x$和$y$必须大于$n$,否则$1/x$或$1/y$就比$1/n$大了。所以不妨令$x=n+a,y=n+b$,其中$a,b$也都是整数。带入原式,我们可以得到$n^2=ab$。所以原方程就变成了$n^2$有多少种方式分解成两数之积。

阅读全文 »

95题链接

28有4个不包含自身的因数1 2 4 7,其和恰好是28,我们称之为完美数。
220不包含自身的的因数之和是284,284不包含自身的因数之和是220,形成了一个长度为2的链,也称之为亲和数。
从12496能形成一个长度为5的链:12496 -> 14288 -> 15472 -> 14536 -> 14264 (-> 12496 -> …)。
找到一个所有数值都不超过一百万的最长的链,问其中最小的数。

首先,我们要快速找到每个数对应的因数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var numberToDivisorSum = new List<int>(MAX + 1);
for (int i = 0; i <= MAX; i++)
{
// 1 is divisor
numberToDivisorSum.Add(1);
}

// i is a factor
for (int i = 2; i <= MAX / 2; i++)
{
// excluding the number itself, so j starts from 2
for (int j = 2; j <= MAX / 2; j++)
{
if (i * j > MAX)
{
break;
}

numberToDivisorSum[i * j] += i;
}
}

接下来计算每个数开始能够形成的链的长度,找到最长链所对应的最小的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
var numberToLength = new List<int>(MAX + 1) { 0 };
int longest = -1;
int index = -1;
for (int i = 1; i <= MAX; i++)
{
numberToLength.Add(0);
if (numberToDivisorSum[i] != -1)
{
int length = GetChainLength(i, numberToDivisorSum);
numberToLength[i] = length;
if (length > longest)
{
index = i;
longest = length;
}
}
}

private static int GetChainLength(int number, List<int> numberToDivisorSum)
{
var chain = new List<int>();
int cur = number;
while (true)
{
chain.Add(cur);
int next = numberToDivisorSum[cur];
if (next > MAX || next == -1)
{
foreach (var s in chain)
{
if (s > number)
{
numberToDivisorSum[s] = -1;
}
}
return -1;
}

if (chain.Contains(next) && number != next)
{
return -1;
}

if (next == number)
{
foreach (var s in chain)
{
if (s > number)
{
numberToDivisorSum[s] = -1;
}
}

return chain.Count;
}

cur = next;
}
}

这里有一个有点trick的地方,如果一个链形成了(已经知道最小数了),或者因数之和比MAX要大导致无法形成一个链,那么把当前number之后的数都标记一下,在外层调用函数的for循环里面跳过,这样子大概能节省10%的时间吧。

145题链接

有这样一些数n,和所以数字逆着写的数reverse(n)之和的所有数字都是奇数。比如36+63=99,409+904=1313等等,这些数我们称之为可逆数。有一个限制条件就是开头不能是0。
问题是,小于十亿(1,000,000,000)的数中有多个可逆数。

这道题可以通过分类讨论来解决。
首先n的长度是奇数和偶数明显是两类,因为这意味着有没有正好居于中间的数,对于奇数长度来说,有,且反过来还是该数字。

我们先来考虑长度是偶数的时候。

长度为2的时候,不妨把该数写作AB,其逆就是BA。以A+B是否大于等于10来讨论。
大于等于10的情况,不妨令A+B=1C,那么AB+BA=1(C+1)C,C和C+1奇偶性必然不同,不可能数字都是奇数。
小于10的情况,那么A+B是奇数。A是偶数,可选2,4,6,8,B是奇数,可选1,3,5,7,9,之和小于10的情况一共10种可能性。反之,A是奇数,B是偶数,也是10种。
所以长度为2的可逆数一共20个。

长度为4的时候,该数可写作ABCD,其逆就是DCBA。以A+D是否大于等于10来讨论。
大于等于10的情况,不妨令A+B=1E。若B+C大于等于10,和最后一位是E,右起第四位是1+E,不可能都是奇数;若B+C小于10,不能是9,否则和的右起第二位是0,不满足题意,如果是其他奇数,右起第二位和1+B+C,而右起第三位是B+C,也不可能同时是奇数。
小于10的情况,A和D的取值可能性有20种,中间的BC退化为长度为2的情况,取值的可能性有30种(偶数可以为0,因为不打头了),利用乘法原则,共有600个可逆数。
所以长度为4的可逆数一共600个。

长度为6的时候,该数可以写作ABCDEF,其逆就是FEDCBA。以A+F是否可以大于等于10来讨论。
大于等于10的情况,原理和4位时一样,B+E不能大于等于10。能小于10吗?为了保证B+E得到的值和E+B+1得到的值一样,那么C+D就要大于10。但是E+B不进位,而D+C进位,导致右起3,4位一定不能同时是奇数。
小于10的情况,中间4个数回到了上一种情况,所以可能性是20*30*30=18,000。
所以长度为6的可逆数一共是18,000个。

长度为8的时候,该数可以写作ABCDEFGH,其逆就是HGFEDCBA。同样,以A+H是否可以大于等于10来讨论。
在大于等于10的情况下,原理同上,B+G不能大于等于10,那么B+G就只能小于10了。同上,C+F就要大于等于10。为了使得中间两位的奇偶性一致,那么E+D要大于10,结果就是右起第三位数字是C+F模10(因为B+G小于10),而右起第六位数字是C+F+1模10,这俩不可能同时是奇数。
小于10的情况,中间六个数字回到了上一种情况,所以可逆数是20*30*30*30=540,000。
所以长度为8的可逆数一共是540,000个。

现在来讨论n的长度为奇数。
如果长度是1,反过来是其本身,那么和是偶数,不符合题意。

长度是3,可写作ABC,可逆数是CBA。中间数字的和是偶数,那么A+C必须大于10,为了右起第一位和第三位奇偶性相同,那么2B不能进位,所以B要小于等于4,那么B有五种可取值;我们现在讨论A和C,A是奇数1,3,5,7,9,C是偶数2,4,6,8,其和大于10的可能性有10中可能性,A是偶数C是奇数也有10种,那么可逆数是5*(10+10)=100。

长度是5时,可写作ABCDE,可逆数是EDCBA。中间是2C,所以B+D是大于等于10的,右起第一位是E+A,但是右起第五位是A+E+1,不可能同时是奇数,所以n的长度不可能是5。

长度为7时,可写作ABCDEFG,可逆数时GFEDCBA。中间是2D,所以C+E时大于等于10的。根据前面的分析,B+F必须小于10;进而2D要小于10。右起第六位会接受来此C+E的进位,那么右起第二位也必须接受一个进位,所以A+G必须大于10。2D小于10得出D有5种可能性,A+G大于10且和为奇数共有20种可能性,C+E大于10且和为奇数也有20种,B+F小于10且为偶数的可能性有25种。所以可逆数是5*20*20*25=50,000。

长度为9的时候,可写作ABCDEFGHI,其可逆数是IHGFEDCBA。由前面的分析可知D+F要大于等于10,那么为了让右起第三位G+C和右起第七位C+G同时为奇数,那么H+B也必须大于10,那么A+I得到B+H的进位,无法和右起第一位I+A同奇偶,矛盾,所以长度不能是9。

综上,小于十亿的可逆数是608720个。

Problem 348

很多数能够写成一个平方数和一个立方数之和的形式,其中一些可能会有多种组合形式。
有一些数有4种组合形式,且它是一个回文数。比如5229225是一个回文数,能写成四种组合形式:

1
2
3
4
2285^2 + 20^3
2223^2 + 66^3
1810^2 + 125^3
1197^2 + 156^3

找到前五小的这种数,求和。

一个数是否能拆解成一个平方数和一个立方数之和是比较难的问题,但是构造一个这样的数就比较简单了。我开始假设在int范围内就至少有五个满足题意的数。
下面这段代码就会找出所有是一个平方数和一个立方数之和的回文数,并且统计了它们出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var counts = new Dictionary<int, int>();
for (int i = 2; i < Math.Sqrt(int.MaxValue); i++)
{
for (int j = 2; j < 1291; j++)
{
long sum = i * i + j * j * j;
if (sum > int.MaxValue)
{
break;
}

int s = (int)sum;
if (Utils.IsPalindrome(s.ToString()))
{
if (counts.ContainsKey(s))
{
counts[s]++;
}
else
{
counts[s] = 1;
}
}
}
}

然后找出出现次数为4的回文数,排序,取前五,求和。

1
2
3
4
var candidates = counts.Where(pair => pair.Value == 4).Select(pair => pair.Key).ToList();
candidates.Sort();

return candidates.Take(5).Sum();