1、算法入门

1、百钱白鸡

我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

• 穷举法 三重循环

    @autoreleasepool {
        int cock,hen,chickhen;
        for (cock=0; cock<=20; cock++) {
            for (hen=0; hen<=33; hen++) {
                for (chickhen=0; chickhen<=100; chickhen++) {
                    if ((cock+hen+chickhen== 100) &&(5*cock+3*hen+chickhen/3==100)) {
                        NSLog(@"%d,%d,%d",cock,hen,chickhen);
                    }
                }
            }
        }
    }

2018-03-31 09:37:38.212963+0800 suanfa1[12882:6077274] 0,25,75
2018-03-31 09:37:38.213225+0800 suanfa1[12882:6077274] 3,20,77
2018-03-31 09:37:38.213243+0800 suanfa1[12882:6077274] 4,18,78
2018-03-31 09:37:38.213282+0800 suanfa1[12882:6077274] 7,13,80
2018-03-31 09:37:38.213303+0800 suanfa1[12882:6077274] 8,11,81
2018-03-31 09:37:38.213339+0800 suanfa1[12882:6077274] 11,6,83
2018-03-31 09:37:38.213354+0800 suanfa1[12882:6077274] 12,4,84

2、借书方案知多少

小明有5本书，要借给 ABC 三个人，每人每次借一本，有多少种方案

• 穷举法 三重循环

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int total=0;
        for (int A=1; A<=5; A++) {
            for (int B=1; B<=5; B++) {
                for (int C=1; C<=5; C++) {
                    if (A!=B && B!=C && A!=C) {
                        NSLog(@"A:%d B:%d C:%d",A,B,C);
                        total++;
                    }
                }
            }
        }
        NSLog(@"共有%d 种方法",total);
    }
    return 0;
}

3、打鱼还是晒网

有一人从1990年1月1日开始，问指定日期是打鱼还是晒网

typedef struct date {
    int year;
    int month;
    int day;
}DATE;
int countDay(DATE);
int runYear(int);
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        DATE today;
        int totalDay;
        int result;
        today.year=2018;
        today.month=4;
        today.day=3;
        totalDay=countDay(today);
        result=totalDay%5;
        if (result>0&&result<5) {
            printf("打鱼");
        }else {
            printf("晒网");
        }
    }
    return 0;
}
int runYear(int year) {
    if((year%4==0 && year%100!=0) || (year%400==0)) {
        return 1;
    }else {
        return 0;
    }
}
int countDay(DATE currentDay) {
    int perMonth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    int totalDay=0,year,i;
    for (year=1990; year<currentDay.year; year++) {
        if (runYear(year)) {
            totalDay+=366;
        }else {
            totalDay+=365;
        }
    }
    if (runYear(currentDay.year)) {
        perMonth[2]+=1;
    }
    for (i=0; i<currentDay.month; i++) {
        totalDay+=perMonth[i];
    }
    totalDay+=currentDay.day;
    return totalDay;
}

4、车牌筛选

该车牌有以下特征：车牌前两位相同，车牌后两位相同，车牌前两位和后两位不相同；车牌是一个整数的平方

• ==对于解不定方程组的问题，一般采取穷举法==

int main(int argc, const char * argv[]) {
    @autoreleasepool {//abcd
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                if (i!=j) {
                    int k = i * 1000 + i * 100 + j * 10 + j;
                    for (int temp=31; temp <=99; temp++) {
                        if (temp * temp == k) {
                            printf("%d\n",k);
                        }
                    }
                }
            }
        }
        for (int A=0; A<=9; A++) {
            for (int B=0; B<=9; B++) {
                for (int C=0; C<=9; C++) {
                    for (int D=0; D<=9; D++) {
                        if (A==B && B!=C && D==C) {
                            int k = A * 1000 + B * 100 + C * 10 + D;
                            for (int temp=0; temp <=99; temp++) {
                                if (temp * temp == k) {
                                    printf("%d%d%d%d",A,B,C,D);
                                }
                            }
                        }
                    }
                    
                }
            }
        }
    }
    return 0;
}

5、兔子产子

有一对兔子，从出生的第3个月起，每月都生一对兔子。小兔子长到3月后每月又生一对兔子，假设所有兔子不死，问30个月内，每月兔子个数是多少。

月份	小兔对数	中兔对数	大兔对数	总兔子对数
1	1	0	0	1
2	0	1	0	1
3	1	0	1	2
4	1	1	1	3
5	2	1	2	5
6	3	2	3	8
7	5	3	5	13

• 兔子的总数构成了Fibonacci 数列
• ==迭代循环：即是一个不断用新值取代变量的旧值，然后由变量旧值递推出变量新值的过程。这种迭代与如下因素有关：初值，迭代公式，迭代此时==

int main(int argc,const char * argv[]) {
    @autoreleasepool {
        int fib1=1;
        int fib2=1;
        for (int mon=3; mon<=30; mon++) {
            int fib = fib1 + fib2;
            printf("%d\n",fib);
            fib1 = fib2;
            fib2 = fib;
        }
    }
    return 0;
}

6.最佳存款方案

假设银行一年整存零取的月息为0.63%。现在某人手中有一笔钱，他打算今后的5年的每年年底取出1000元，到第5年时刚好取完，请算出他存钱时应存入多少。

第5年年初的初款歀数=1000/(1+12*0.0063) 
第4年年初的初款歀数=（第5年年初的初款歀数+1000）/(1+12*0.0063) 
第3年年初的初款歀数=（第4年年初的初款歀数+1000）/(1+12*0.0063) 
第2年年初的初款歀数=（第3年年初的初款歀数+1000）/(1+12*0.0063) 
第1年年初的初款歀数=（第2年年初的初款歀数+1000）/(1+12*0.0063)


int main(int argc,const char * argv[]) {
    @autoreleasepool {
        double money=0;
        for (int i=0; i<5; i++) {
            money=(money+1000)/(1+12*0.0063);
        }
        printf("%f",money);
    }
    return 0;
}

7、冒泡排序

冒泡排序是在两个相邻元素之间进行比较。交换的过程是将一个无序表变成有序表。

冒泡排序的思想：首先，从表头开始扫描数组，在扫描过程中，逐对进行比较相邻两个元素的大小，若相邻两个元素中，前面的元素大于后面的元素,则将他们交换，称为==消去了一个逆序==。在扫描过程中，不断将两相邻元素中的大数往后移动，最后就将数组中最大的元素换到了最后。然后将剩下的 n-1个元素重复上述过程，直到剩下的元素为0为止。

//冒泡排序
int main(int argc,const char * argv[]) {
    @autoreleasepool {
        int arr[] ={12,10,8,9,11,7};
        for (int i=0; i<6-1; i++) {//共比较5轮
            for (int j=0; j<6-1-i; j++) {//每轮比较的次数
                if(arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        for (int i=0; i<6; i++) {
            printf("%d\n",arr[i]);
        }
    }
    return 0;
}

image

8、折半查找

二分查找法（也叫折半查找法），本质是分治算法的一种，所谓分治算法，指的是分而治之，即将一个较大规模的问题分解成几个较小规模的问题，这些子问题互相独立且与原问题相同，通过对较小规模问题的求解，达到对整个问题的求解。当我们把问题分解成两个较小问题求解时的分治方法称为二分法。==需要注意的是，二分查找法只适用于有序序列。==

image

//折半查找
int main(int argc,const char * argv[]) {
    @autoreleasepool {
        int arr[] ={-2,10,28,39,41,67,78,102,308,500};//10个数
        int low=0;
        int high=10-1;
        int mid=0;
        int find=102;//要查找的数字
        int k=-1;
        while(low <= high) {//继续查找的条件
            mid=(low+high)/2;
            if (find<arr[mid]) {
                high=mid-1;
            }else {
                if (find>arr[mid]) {
                    low=mid+1;
                }else {
                    k=mid;
                    break;
                }
            }
        }
        if (k>=0) {
            printf("%d在数组的下标位%d\n",find,k);
        }else {
            printf("%d在数组没有发现\n",find);
        }
        
    }
    return 0;
}

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数！
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O(h)=O(log2n)

9、进制的转换

image

//进制转换
#define MAXCHAR 101 //最大允许的字符串长度
int char_to_number(char ch);//字符转数字
char num_to_char(int num);//数字转字符
long source_to_decimal(char temp[],int source);//数组转10进制数
int decimal_to_object(char temp[],long decimal_num,int object);//返回转换成其他进制后字符串的长度
void output(char temp[],int length);//数组逆序打印
int main(int argc,const char * argv[]) {
    @autoreleasepool {
        int source;//原数进制
        int object;//存储目标进制
        int length;//转换成目标进制后数组的长度
        long decimal_num;//转换成的10进制数
        char temp[MAXCHAR];//存储待转换和转换后的数组
        int flag=1;//程序是否退出
        while (flag) {
            printf("转换前的数字是：");
            scanf("%s",temp);
            printf("转换前的进制是：");
            scanf("%d",&source);
            printf("转换后的进制是：");
            scanf("%d",&object);
            printf("转换后的数字是：");
            decimal_num=source_to_decimal(temp, source);
            length=decimal_to_object(temp, decimal_num, object);
            output(temp, length);
            printf("继续输入1，退出输入0\n");
            scanf("%d",&flag);
        }
    }
    return 0;
}
int char_to_number(char ch) {
    if (ch>='0'&&ch<='9') {
        return ch-'0';
    }else {
        return ch-'A'+10;
    }
}
char num_to_char(int num) {
    if (num>=0&&num<=9) {
        return (char)('0'+num-0);
    }else {
        return (char)('A'+num-10);
    }
}
long source_to_decimal(char temp[],int source) {
    long decimal_num=0;
    int length=0;
    int i;
    for (i=0; temp[i]!='\0'; i++) {
        length=i;
    }
    for (i=0; i<=length; i++) {
        decimal_num=(decimal_num*source)+char_to_number(temp[i]);
    }
    printf("-------------");
    printf("%ld\n",decimal_num);
    return decimal_num;
}
int decimal_to_object(char temp[],long decimal_num,int object){
    int i=0;
    while (decimal_num) {
        temp[i]=num_to_char(decimal_num%object);
        decimal_num=decimal_num/object;
        i++;
    }
    temp[i]='\0';
    return i;
}
void output(char temp[],int length) {
    int i=0;
    for (i=length-1; i>=0; i--) {
        printf("%c",temp[i]);
    }
    printf("\n");
}