美文网首页
1、算法入门

1、算法入门

作者: 元宝是只小肥猫 | 来源:发表于2018-04-17 19:10 被阅读23次

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");
}

相关文章

  • 1、算法入门

    1、百钱白鸡 我国古代数学家张丘建在《算经》一书中提出的数学问题:鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买...

  • 算法入门(1)

    ** 以下都是通过枚举法解决问题的。其实枚举法的本质就是把所有问题可能的结果都尝试一边,再通过某种条件将错误的结果...

  • 学习路线规划

    目前有两本书,《算法竞赛入门经典》和《算法竞赛进阶指南》。根据书名应该先看《算法竞赛入门经典》( 《算法竞赛入门经...

  • Python 入门之 内置模块 -- hashlib模块

    Python 入门之 内置模块 -- hashlib模块 1、hashlib 摘要算法,加密算法 (1)主要用途:...

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • 自学资源整理--干货

    算法学习 书籍: 1、算法图解 Aditya Bhargava (作者) 袁国忠(译者) ——在非常适合入门,简单...

  • 十秒钟入门C语言—算法初窥

    // main.c// 算法入门1//// Created by tarena on 15/5/28.// ...

  • 算法与数据结构」整理推荐书单2019-06-29

    从入门到进阶吐血整理推荐书单 1,《图解算法》 编得比较走心,适合饭后翻翻看看的一本入门算法书! 2,《Probl...

  • 推荐算法入门

    推荐算法入门 1. 推荐算法知识架构 ​ 推荐算法有很多种,大体上可以将推荐算法分为以下几种: 协同过滤推荐算...

  • 《算法竞赛入门经典(第2版) 算法艺术与信息学竞赛》PDF高清完

    《算法竞赛入门经典(第2版) 算法艺术与信息学竞赛》PDF高清完整版-免费下载 《算法竞赛入门经典(第2版) 算法...

网友评论

      本文标题:1、算法入门

      本文链接:https://www.haomeiwen.com/subject/txvpkftx.html