闲来没事自己学学算法，从最简单的开始。

19头牛

问题描述:有一个老人在临死前把三个儿子叫到跟前,告诉他们把19头牛分了,老大分1/2,老二分1/4,老三分1/5,说完就死了.按当地习俗,不能宰牛.问三个儿子各能分多少?
问题分析:由于19与2、4、5都不能整除,所以就不能用平常的方法来解决这个问题。但是,如果仔细一点就可以发觉到:1/2+1/4+1/5=19/20,而牛的数量刚好为19。
swift写法：

<pre> func shareCow() {
for i in 1..<11{ //遍历查找
if i + i / 2 + 2 * (i / 5) == 19{ //找到满足条件的个数
print("三个儿子分别分得: (i) (i / 2) (2 * i / 5)")

        }
    }
}

</pre>

C语言写法:
<pre>

include <stdio.h>

int main()
{
int i;
for (i=1; i<=10; i++) //遍历查找
{
if (i + i/2 + 2i/5 == 19) //找到满足条件的个数
{
printf("三个儿子分别分得:%d头，%d头，%d头", i, i/2, 2i/5);
}
}
return 0;
}
//打印结果<p style="margin-top: 0px; margin-bottom: 0px; ">三个儿子分别分得:10头，5头，4头</p> </pre>

分钱

问题描述：一元钱分成1分、2分、5分的,问有多少种分法?
问题分析：从题目就能看出，分发肯定是有很多种，常规的逐个判断显然不适合。考虑到不是所有的面值都得用到，并且1分得特殊性（最小因子）。我们先从5分开始考虑，遍历5分所有可能个数，然后制约2分的个数，最后1分的无需考虑，缺了全部补一分的就行了。
swift写法:

func shareMoney() {
var count = 0
for i in 0..<21{ //遍历5分的所有情况。 0<=i<=20
for _ in 0..<(100 - 5 * i) / 2 + 1{ //制约2分的可能情况 一
count += 1 //二
} //三
}
// 或者。上述 一二三语句可以替换成如下语句
// for j in 0..<51{
// if 5 * i + j * 2 <= 100{
// count += 1
// }
// }
print("共有(count)种分法")
}

C语言写法:

<pre>#include <stdio.h>

int main()
{
int i, j;
int count_ = 0;

for (i=0; i<=20; i++)   //遍历5分的所有情况。 0<=i<=20  
{  
    for (j=0; j<=(100-5*i)/2; j++)  //制约2分的可能情况  一  
    {  
        count_++;                                  //二  
    }                                            //三  
      
    //或者。上述 一二三语句可以替换成如下语句  
    //for (j=0; j<=50; j++)  
    //{  
    //    if (5*i + j*2 <= 100)  
    //    {  
    //        count_++;  
    //    }  
    //}  
}  
  
printf("共有%d种分法", count_);  

return 0;  

}

//打印结果 共有541种分法 </pre>

队列人数

swift写法：

<pre>func queueUp() {
var i = 9
while(i <= 7000){
for k in stride(from: 9, through: 1, by: -1){

            if (i + 1) % k != 0{
                break
            }
            if k == 1{
                print("乐队共有\(i)人")
                return             //找到最小的
            }
        }
        i += 10
    }
}

</pre>

C语言写法：

<pre>#include <stdio.h>

int main()
{
int i, j;
for (i=9; i<=7000; i+=10) //用最大步长取最外层循环变量值
{
for (j=9; j>=2; j--) //模拟排队过程
{
if ((i+1)%j != 0) //不满足条件
{
break;
}
}
if (j==1) //满足条件
{
printf("乐队共有%d人", i);
return 0; //找到最小的
}

}  

return 0;  

}
//打印结果 乐队共有2519人 </pre>

里程碑种数

问题描述：甲、乙两个城市有一条999公里长的公路。公路旁每隔一公里竖立着一个里程碑,里程碑的半边写着距甲城的距离,另半边写着距乙城的距离。有位司机注意到有的里程碑上所写的数仅用了两个不同的数字,例如000/999仅用了0和9,118/881仅用了1和8。算一算具有这种特征的里程碑共有多少个,是什么样的?
问题分析：从题意中可知每对数仅用了两个不同的数字,并且两个数字之和衡等于9.并且,每对数之和也应衡等于999. 通过这两个限制条件，我们也不难写出代码。
swift写法：

<pre>func milestoneCount() {
var sum = 0
var count = 0
for i in 0..<10{
for j in 0..<10{
for k in 0..<10{
if (((i==j)&&(9-i==k))||((i==k)&&(9-i==j))||((j==k)&&(9-k==i))||((i==j)&&(j==k))){
sum = i * 100 + j * 10 + k
print("(sum) / (999 - sum)")
count += 1
}
}
}
}
print("满足里程碑个数: (count)")
}
</pre>

C语言写法：

<pre>#include <stdio.h>

int main()
{
int i, j, k, sum_, count_ = 0;

for (i=0; i<=9; i++)  
{  
    for (j=0; j<=9; j++)  
    {  
        for (k=0; k<=9; k++)  
        {  
            if (((i==j)&&(9-i==k))||((i==k)&&(9-i==j))||((j==k)&&(9-k==i))||((i==j)&&(j==k)))  
            {  
                sum_ = i*100 + j*10 + k;  
                printf("%d---%d\n", sum_, 999-sum_);  
                count_++;  
            }  
        }  
    }  
}  
  
printf("满足条件的里程碑个数: %d", count_);  

return 0;  

}

//打印结果 满足条件的里程碑个数: 40 （具体省略） </pre>

同等遗产

问题描述：父亲临终时,让按下列方式分配他的遗产:大儿子分得100克朗和剩下财产的1/10,二儿子分得200克朗和剩下财产的1/10,三儿子分得300克朗和剩下财产的1/10。依此类推,最后发现这种分法好极了,因为所有儿子分得的钱数恰好相等。问他共有几个儿子?每个儿子分得多少遗产?
swift写法：

<pre>func equalHeritage() {
var i = 2
var k = 0
var m: Int!
var n: Int = 600
while (n > 0) {
k = 100 + (n - 100) / 10
m = n - k
while (m > 0) {
if ((m % 10 != 0) || (k != i * 100 + (m - i * 100) / 10)){
break
}else {
m = (m - i * 100) - (m - i * 100) / 10
}
i += 1
}
if m == 0 {
print("他共有(i)个儿子，每个儿子分(k)克朗")
}
n += 10
}
}
</pre>

C语言写法：

<pre>#include <stdio.h>

int main()
{
int i, j, k, m, n;
for (n=600; ; n=n+10) //由题意得，遗产最少600，并且最小步长10
{
k = 100 + (n-100)/10; //遍历寻找满足条件的
m = n - k; //每个儿子遗产都一样，直接利用大儿子分得的带入计算
for (i=2; m>0; i++)
if ((m%10!=0)||(k!=i100+(m-i100)/10))
break;
else m = (m-i100) - (m-i100)/10;
if (m==0)
{
printf("他共有%d个儿子,每个儿子分得%d克朗.", i, k);
exit(0); //找出后退出程序，不然无限循环
}
}
return 0;
}

//打印结果 他共有10个儿子,每个儿子分得900克 </pre>

寻找丑数

问题描述: 我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。
分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。
所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以连续5。如果最后我们得到的是1，那么这个数就是丑数，否则不是。
基于前面的分析，我们可以写出如下的函数来判断一个数是不是丑数：
swift写法：

<pre>func isUgly(number: Int) -> Bool {
var number = number
while number % 2 == 0 {
number /= 2
}
while number % 3 == 0 {
number /= 3
}
while number % 5 == 0 {
number /= 5
}
return number == 1 ? true : false
}

func getUglyNumberSolution(index: Int) -> Int {
    if index <= 0{
        return 0
    }
    var number = 0
    var uglyFound = 0
    while uglyFound < index {
        number += 1
        if isUgly(number: number){
            uglyFound += 1
        }
    }
    return number
}

</pre>

话说用swift写这个，1500的话执行时间大概40多秒，不建议这么写。
C语言写法：

<pre>
bool IsUgly(int number)
{
while(number % 2 == 0)
number /= 2;
while(number % 3 == 0)
number /= 3;
while(number % 5 == 0)
number /= 5;
return (number == 1) ? true : false;
}

接下来，我们只需要按顺序判断每一个整数是不是丑数，即：

int GetUglyNumber_Solution1(int index)
{
if(index <= 0)
return 0;
int number = 0;
int uglyFound = 0;
while(uglyFound < index)
{
++number;
if(IsUgly(number))
{
++uglyFound;
}
}
return number;
} </pre>

这个算法可以改进效率更高：
我们只需要在函数GetUglyNumber_Solution1中传入参数1500，就能得到第1500个丑数。该算法非常直观，代码也非常简洁，但最大的问题我们每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高。
接下来我们换一种思路来分析这个问题，试图只计算丑数，而不在非丑数的整数上花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。
这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者。
前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，存在着同样的T3和T5。
有了这些分析，我们不难写出如下的代码：

<pre>int GetUglyNumber_Solution2(int index)
{
if(index <= 0)
return 0;
int *pUglyNumbers = new int[index];
pUglyNumbers[0] = 1;
int nextUglyIndex = 1;
int *pMultiply2 = pUglyNumbers;
int pMultiply3 = pUglyNumbers;
int pMultiply5 = pUglyNumbers;
while(nextUglyIndex < index)
{
int min = Min(pMultiply2 * 2, pMultiply3 * 3, pMultiply5 * 5);
pUglyNumbers[nextUglyIndex] = min;
while(pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
++pMultiply2;
while(pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
++pMultiply3;
while(pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
++pMultiply5;
++nextUglyIndex;
}
int ugly = pUglyNumbers[nextUglyIndex - 1];
delete[] pUglyNumbers;
return ugly;
}
int Min(int number1, int number2, int number3)
{
int min = (number1 < number2) ? number1 : number2;
min = (min < number3) ? min : number3;
return min;
} </pre>

和第一种思路相比，这种算法不需要在非丑数的整数上做任何计算，因此时间复杂度要低很多。感兴趣的读者可以分别统计两个函数GetUglyNumber_Solution1(1500)和GetUglyNumber_Solution2(1500)的运行时间。当然我们也要指出，第二种算法由于要保存已经生成的丑数，因此需要一个数组，从而需要额外的内存。第一种算法是没有这样的内存开销的。

河内之塔(Hanoi)

问题描述:说明河内之塔(Towers ofHanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 EdouardLucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。
问题分析: 解法如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘子,就将B当作辅助柱。如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,也就是:A->B、A ->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式的递回处理。事实上,若有n个盘子,则移动完毕所需之次数为2^n - 1,所以当盘数为64时,则所需次数为:264- 1 =18446744073709551615为5.05390248594782e+16年,也就是约5000世纪,如果对这数字没什幺概念,就假设每秒钟搬一个盘子好了,也要约5850亿年左右。

<pre>func move(n:Int, a: String, b: String) {
print("(n): (a)--->(b)")
}

func hanoi(n: Int, a: String, b: String, c: String) {
    if n == 1{
        move(n: n, a: a, b: c)
    }else{
        hanoi(n: n - 1, a: a, b: c, c: b)
        move(n: n, a: a, b: c)
        hanoi(n: n - 1, a: b, b: a, c: c)
    }
}

</pre>

Algorithm Gossip: 费式数列

问题描述: 说明Fibonacci为1200年代的欧洲数学家,在他的著作中曾经提到:「若有一只免子每个月生一只小免子,一个月后小免子也开始生产。起初只有一只免子,一个月后就有两只免子,二个月后有三只免子,三个月后有五只免子(小免子投入生产)......。如果不太理解这个例子的话,举个图就知道了,注意新生的小免子需一个月成长期才会投入生产,类似的道理也可以用于植物的生长,这就是Fibonacci数列,一般习惯称之为费氏数列,例如以下: 1、1 、2、3、5、8、13、21、34、55、89......
问题分析:解法依说明,我们可以将费氏数列定义为以下:
<pre>
f(n) = f(n-1)+f(n-2)---- if n>1
f(n) = n ------if n = 0, 1
</pre>

斐波那契数列，应该是每个写代码的都接触过了。虽然简单，不过还是罗列出来，谁叫它经典呢。

<pre>func fibonacciSequence() {
// let n = 10
var fibArr = [Int](repeating: 0, count:10)
fibArr[0] = 0
fibArr[1] = 1

    for i in 2..<10{
        fibArr[i] = fibArr[i - 1] + fibArr[i - 2]
    }
    for i in 0..<10{
        print("\(fibArr[i])  ")
    }
}</pre>

三色旗

问题描述:三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。
问题分析: 在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移

只是要让移动次数最少的话，就要有些技巧：

w作为当前元素的下标，而b则表示下标在b之前的旗子颜色都是蓝色，r表示下标在r后面的都是红色，不符合这个条件的，就交换。
什么时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。 如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。

<pre>var cArr = ["r","b","w","w","b","b","b","r","w","r"]
func swap(i: Int, j: Int) {
let tempArr = cArr[i]
cArr[i] = cArr[j]
cArr[j] = tempArr
}

func moveFlag() {
    var w = 0
    var b = 0
    var r = cArr.count - 1
    
    while w <= r {
        switch cArr[w]{
            case "w":
                w += 1
            case "b":
                swap(i: w, j: b)
                w += 1
                b += 1
            case "r":
                swap(i: w, j: r)
                r -= 1
             default: break
        }
    }
    print(cArr)
}

</pre>