贪心算法总结

Ⅰ 活动安排问题，贪心算法Greedyselector 却总能求得整体的最优解，这个能用数学归纳法证明 求大侠指导

贪心算法Greedyselector
第n + 1次select都比第 n 次更优
n 趋于 无限 的时候 总能得到最优解

Ⅱ 用动态规划解决钢条切割问题时，它的最优子结构是什么

1、两种重要算法思想： 动态规划，贪心算法
2、动态规划：
基本原理：动态规划英文名dynamic programming。其中pogramming指的是表格法，而非编写计算机程序。因此，可以初步得出动态规划的基本思想：将一个具有最优子结构性质的问题分成若干个子问题，在求解过程中，记录下子问题的结果，存储在一个表格中，使得公共的子问题只需要计算一次。书中给出的基本原理：动态规划将问题分成若干个相互重叠的子问题，递归的求解子问题，保存子问题的解，再将它们的解组合起来，求出原问题的解。
从基本原理中可以看出动态规划需要满足两个条件，最优子结构和子问题重叠。
最优子结构：书中定义：问题的最优解由相关子问题的最优解组合而成，一个问题的最优解包含其子问题的最优解。典型的有背包问题和钢条切割我问题。所谓子问题就是一中组合，将一个问题分成许多子问题的集合。某个子问题转化为问题时，所需要的代价是固定的。
一般这类问题的解题过程：（自己总结）
画出子问题图（类似于逆拓扑排序的图，子问题必须在问题前面完成）
用数学表达式构建出问题的最优解和子问题最优解之间的代数表达式
通常采用自底向上的方法进行递归地求解问题的解，自底下上的含义是从最小的子问题求起。
保存每一步求出的子问题的最优解
利用计算出的信息构造一个最优解

Ⅲ 求一个算法(贪心算法)

首先,无所谓哪里密集哪里不密集的说法,这是人为的区分,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了.
既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走，思想如下:
判断当前格子右、下两个相邻的格子是否有金块，情形如下：
1）如果一个有一个没有，则往有金块的格子走
2）如果都没有或都有，则需要判断往哪个方向走能更快的拾到下一个金块，方法如下：
让机器人假设地各往两个方向走一步，然后对当前格子作判断情形如下：
A)一个格子继续走能拾到金块，另一个不能，则上一步往该格子走
B)如果仍旧都有或都没有，重复2）直到找到符合A）的情形。

假设棋盘是N*N个格子，则贪心算法最坏的情形是要遍历整个棋盘，比如只有第一个格子有金块时，就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4*N个格子。
时间复杂度上来算的话，应该是O（nLogn）

Ⅳ 求份 贪心算法报告 用C，C++ 或JAVA

同学啊，明天就要交了，如果真的不知道怎么写，我给你个及格分吧。不用来这里求助的啦

Ⅳ 研究贪心算法和动态规划算法的目的和意义

动态规划和贪心算法都是一种递推算法
均有局部最优解来推导全局最优解

不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解

Ⅵ 学习C语言需要掌握哪些基本知识

1.入门程序

#include <stdio.h>
int main()
{
printf("Hello World!");
return 0;
}

2.数据类型

数据类型:

1.基本数据类型：

1.1. 整型:int 4个字节

1.2. 字符型:char 1个字节

1.3. 实型(浮点型)

• 1.3.1.单精度型:float 4个字节

• 1.3.2.双精度型:double 8个字节

2.构造类型：

2.1.枚举类型

2.2.数组类型

2.3.结构体类型

2.4.共用体类型

3.指针类型：

4.空类型：

3.格式化输出语句

• %d:十进制整数;

• %c:单个字符;

• %s:字符串;

• %f:6位小数;

• #include <stdio.h>


• int main()


• {


• int age = 18;


• float height = 1.85;


• char unit = 'm';


• printf("小明今年%d岁 ", age);


• printf("小明身高%f%c ", height, unit);


• printf("小明现在在慕课网上学习IT技术 ");


• return 0;


• }



学好C++才是入职大厂的敲门砖！ 当年要是有这课，我的C++也不至于这样

已失效

4.常量

值不发生改变的量成为常量;

定义字符常量(注意后面没有;)

• #include <stdio.h>


• #define POCKETMONEY 10 //定义常量及常量值


• int main()


• {


• printf("小明今天又得到%d元零花钱 ", POCKETMONEY);


• return 0;


• }



5.运算符

5.1.算数运算符:+,-,*,/,%,++,--;前++/--,先运算,再取值.后++/--,先取值,再运算;

5.2.赋值运算符:

5.3.关系运算符;

5.4.逻辑运算符;

5.5.三目运算符:

• 表达式1 ? 表达式2 : 表达式3;

6.水仙花数计算

输出所有三位数的水仙花数字

所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数，如：153就是一个水仙花数，153=111+555+333。

• #include <stdio.h>



• int main()


• {


• //定义三位数num,个位数sd,十位数td,百位数hd


• int num, sd, td, hd;


• //循环所有三位数


• for( num=100 ; num<1000 ; num++ )


• {


• //获取三位数字num百位上的数字


• hd = num/100 ;


• //获取三位数字num十位上的数字


• td = num/10%10 ;


• //获取三位数字num个位上的数字


• sd = num%10 ;


• //水仙花数的条件是什么？


• if(num ==hd*hd*hd+td*td*td+sd*sd*sd )


• {


• printf("水仙花数字：%d ", num);


• }


• }


• return 0;


• }



7.打印正三角形的*

• #include <stdio.h>


• int main()


• {


• int i, j, k;


• for(i=1; i<5; i++)


• {


• /* 观察每行的空格数量，补全循环条件 */


• for( j=i ; j<5 ; j++ )


• {


• printf(" "); //输出空格


• }


• /* 观察每行*号的数量，补全循环条件 */


• for( k=0 ; k<2*i-1 ; k++ )


• {


• printf("*"); //每行输出的*号


• }


• printf(" "); //每次循环换行


• }


• return 0;


• }



8.臭名远扬的goto语句

很少使用

• #include <stdio.h>


• int main()


• {


• int sum = 0;


• int i;


• for(i=1; i<=10; i++)


• {


• printf("%d ", i);


• if(i==3){


• goto LOOP;//满足条件就执行goto语句


• }


• }


• //执行goto


• LOOP:printf("结束for循环了...."); //请选择合适位置添加标识符


• return 0;


• }



9.形参与实参

形参:形参是在定义函数名和函数体的时候使用的参数,目的是用来接收调用该函数时传入的参数;

实参:实参是在调用时传递该函数的参数。

函数的形参和实参具有以下特点：

• 形参只有在被调用时才分配内存单元，在调用结束时，即刻释放所分配的内存单元。因此，形参只有在函数内部有效。函数调用结束返回主调函数后则不能再使用该形参变量。

• 实参可以是常量、变量、表达式、函数等，无论实参是何种类型的量，在进行函数调用时，它们都必须具有确定的值，以便把这些值传送给形参。因此应预先用赋值等办法使实参获得确定值。

• 在参数传递时，实参和形参在数量上，类型上，顺序上应严格一致，否则会发生类型不匹配”的错误。

10.函数返回值注意

注意：void函数中可以有执行代码块，但是不能有返回值，另void函数中如果有return语句，该语句只能起到结束函数运行的功能。其格式为：return;

11.递归

• #include <stdio.h>



• int getPeachNumber(int n) //这里要定义n，要不编译器会报错！


• {


• int num;


• if(n==10)


• {


• return 1;


• }


• else


• {


• num = (getPeachNumber(n+1)+1)*2;


• printf("第%d天所剩桃子%d个 ", n, num);


• }


• return num;


• }


• int main()


• {


• int num = getPeachNumber(1);


• printf("猴子第一天摘了:%d个桃子。 ", num);


• return 0;


• }



12.变量存储类别 !

12.1.生存周期划分存储方式

C语言根据变量的生存周期来划分，可以分为静态存储方式和动态存储方式。

静态存储方式：是指在程序运行期间分配固定的存储空间的方式。静态存储区中存放了在整个程序执行过程中都存在的变量，如全局变量。

动态存储方式：是指在程序运行期间根据需要进行动态的分配存储空间的方式。动态存储区中存放的变量是根据程序运行的需要而建立和释放的，通常包括：函数形式参数；自动变量；函数调用时的现场保护和返回地址等。

12.2.存储类型划分

C语言中存储类别又分为四类：自动（auto）、静态（static）、寄存器的（register）和外部的（extern） ;

• 用关键字auto定义的变量为自动变量，auto可以省略，auto不写则隐含定为“自动存储类别”，属于动态存储方式。

• 用static修饰的为静态变量，如果定义在函数内部的，称之为静态局部变量；如果定义在函数外部，称之为静态外部变量。

注意：静态局部变量属于静态存储类别，在静态存储区内分配存储单元，在程序整个运行期间都不释放；静态局部变量在编译时赋初值，即只赋初值一次；如果在定义局部变量时不赋初值的话，则对静态局部变量来说，编译时自动赋初值0（对数值型变量）或空字符（对字符变量）

• 为了提高效率，C语言允许将局部变量的值放在CPU中的寄存器中，这种变量叫“寄存器变量”，用关键字register作声明。

注意：只有局部自动变量和形式参数可以作为寄存器变量；一个计算机系统中的寄存器数目有限，不能定义任意多个寄存器变量；局部静态变量不能定义为寄存器变量。

• 用extern声明的的变量是外部变量，外部变量的意义是某函数可以调用在该函数之后定义的变量。

• #includ <stdio.h>


• //来源公众号：C语言与CPP编程


• int main()


• {


• //定义外部局部变量


• extern int x;


• return 0;


• }


• int x=100;



13.内部函数外部函数 !

在C语言中不能被其他源文件调用的函数称为内部函数 ，内部函数由static关键字来定义，因此又被称为静态函数，形式为：

static [数据类型] 函数名（[参数]）

这里的static是对函数的作用范围的一个限定，限定该函数只能在其所处的源文件中使用，因此在不同文件中出现相同的函数名称的内部函数是没有问题的。

在C语言中能被其他源文件调用的函数称为外部函数 ，外部函数由extern关键字来定义，形式为：

extern [数据类型] 函数名([参数])

C语言规定，在没有指定函数的作用范围时，系统会默认认为是外部函数，因此当需要定义外部函数时extern也可以省略。 extern可以省略; 14.数组 数组:一块连续的，大小固定并且里面的数据类型一致的内存空间， 数组的声明:数据类型 数组名称[长度n]

• 数据类型 数组名称[长度n] = {元素1,元素2,元素3,......};

• 数据类型 数组名称[] = {元素1,元素2,元素3,......};

• 数类类型 数组名称[长度n]; 数组名称[0] = 元素1;数组名称[1] = 元素2;...... 注意： 1、数组的下标均以0开始； 2、数组在初始化的时候，数组内元素的个数不能大于声明的数组长度； 3、如果采用第一种初始化方式，元素个数小于数组的长度时，多余的数组元素初始化为0； 4、在声明数组后没有进行初始化的时候，静态（static）和外部（extern）类型的数组元素初始化元素为0，自动（auto）类型的数组的元素初始化值不确定。

15.数组遍历

• #include <stdio.h>



• int main()


• {


• int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};


• int i;


• for(i=0;i<10;i++)


• {


• printf("%d ",arr[i]);


• }


• return 0;


• }



• 数组的冒泡排序

冒泡排序的思想：相邻元素两两比较，将较大的数字放在后面，直到将所有数字全部排序。

• 字符串与数组

在C语言中,是没有办法直接定义子字符串数据类型的,需使用数组来定义所要的字符串,形式如下:

• char 字符串名称[长度] = "字符串内容";

• char 字符串名称[长度] = {'字符串1','字符串2',....,'字符串n',''};

注:

• []中的长度可以省略不写;

• 采用第二种方式最后一个元素必须是'',表示结束;

• 第二种方式不能写中文!; 输出字符串时,要使用:printf("%s",字符数组名);或puts(字符数组名);

16.字符串函数

• strlen(s):获取字符串s的长度;

• strcmp(s1,s2):比较字符串;比较的时候会把字符串转换成ASCII码再进行比较,返回结果为0表示s1和s2的ASCII码值相等,返回结果为1表示s1比s2的ASCII码大,返回结果为-1表示s1比s2的ACSII码小;

• strcpy(s1,s2):字符串拷贝;s2会取代s1中的内容;

• strcat(s1,s2)将s2拼接到s1后面;注意:s1的length要足够才可以!

• atoi(s1)将字符串转为整数!

17.多维数组

数据类型 数组名称[常量表达式1]...[常量表达式n];

多维数组的初始化与一维数组的初始化类似也是分两种：

• 数据类型 数组名称[常量表达式1][常量表达式2]...[常量表达式n] = {{值1,..,值n},{值1,..,值n},...,{值1,..,值n}};

• 数据类型 数组名称[常量表达式1][常量表达式2]...[常量表达式n]; 数组名称[下标1][下标2]...[下标n] = 值;

多维数组初始化要注意以下事项：

• 采用第一种始化时数组声明必须指定列的维数。因为系统会根据数组中元素的总个数来分配空间，当知道元素总个数以及列的维数后，会直接计算出行的维数；

• 采用第二种初始化时数组声明必须同时指定行和列的维数。

18.多维度数组的遍历

使用嵌套循环

注意:多维数组的每一维下标均不能越界!

19.结构体

C 数组允许定义可存储相同类型数据项的变量，结构是 C 编程中另一种用户自定义的可用的数据类型，它允许您存储不同类型的数据项。

结构用于表示一条记录，假设您想要跟踪图书馆中书本的动态，您可能需要跟踪每本书的下列属性：

• Title

• Author

• Subject

• Book ID

定义结构

为了定义结构，您必须使用 struct 语句。struct 语句定义了一个包含多个成员的新的数据类型，struct 语句的格式如下：

• struct tag {


• member-list


• member-list


• member-list


• ...


• } variable-list ;



tag 是结构体标签。

member-list 是标准的变量定义，比如 int i; 或者 float f，或者其他有效的变量定义。

variable-list 结构变量，定义在结构的末尾，最后一个分号之前，您可以指定一个或多个结构变量。下面是声明 Book 结构的方式：

• struct Books


• {


• char title[50];


• char author[50];


• char subject[100];


• int book_id;


• } book;



在一般情况下，tag、member-list、variable-list 这 3 部分至少要出现 2 个。以下为实例：

• //此声明声明了拥有3个成员的结构体，分别为整型的a，字符型的b和双精度的c


• //同时又声明了结构体变量s1


• //这个结构体并没有标明其标签


• struct


• {


• int a;


• char b;


• double c;


• } s1;




• //此声明声明了拥有3个成员的结构体，分别为整型的a，字符型的b和双精度的c


• //结构体的标签被命名为SIMPLE,没有声明变量


• struct SIMPLE


• {


• int a;


• char b;


• double c;


• };


• //用SIMPLE标签的结构体，另外声明了变量t1、t2、t3


• struct SIMPLE t1, t2[20], *t3;




• //也可以用typedef创建新类型


• typedef struct


• {


• int a;


• char b;


• double c;


• } Simple2;


• //现在可以用Simple2作为类型声明新的结构体变量


• Simple2 u1, u2[20], *u3;



访问结构成员

为了访问结构的成员，我们使用成员访问运算符（.）。成员访问运算符是结构变量名称和我们要访问的结构成员之间的一个句号。您可以使用 struct 关键字来定义结构类型的变量。下面的实例演示了结构的用法：

• #include <stdio.h>


• #include <string.h>


• //来源公众号：C语言与CPP编程




• struct Books


• {


• char title[50];


• char author[50];


• char subject[100];


• int book_id;


• };




• int main( )


• {


• struct Books Book1; /* 声明 Book1，类型为 Books */


• struct Books Book2; /* 声明 Book2，类型为 Books */




• /* Book1 详述 */


• strcpy( Book1.title, "C Programming");


• strcpy( Book1.author, "Nuha Ali");


• strcpy( Book1.subject, "C Programming Tutorial");


• Book1.book_id = 6495407;




• /* Book2 详述 */


• strcpy( Book2.title, "Telecom Billing");


• strcpy( Book2.author, "Zara Ali");


• strcpy( Book2.subject, "Telecom Billing Tutorial");


• Book2.book_id = 6495700;




• /* 输出 Book1 信息 */


• printf( "Book 1 title : %s ", Book1.title);


• printf( "Book 1 author : %s ", Book1.author);


• printf( "Book 1 subject : %s ", Book1.subject);


• printf( "Book 1 book_id : %d ", Book1.book_id);




• /* 输出 Book2 信息 */


• printf( "Book 2 title : %s ", Book2.title);


• printf( "Book 2 author : %s ", Book2.author);


• printf( "Book 2 subject : %s ", Book2.subject);


• printf( "Book 2 book_id : %d ", Book2.book_id);




• return 0;


• }



学好C++才是入职大厂的敲门砖！ 当年要是有这课，我的C++也不至于这样

已失效

20.共用体

共用体是一种特殊的数据类型，允许您在相同的内存位置存储不同的数据类型。您可以定义一个带有多成员的共用体，但是任何时候只能有一个成员带有值。共用体提供了一种使用相同的内存位置的有效方式。

• #include <stdio.h>


• #include <string.h>




• union Data


• {


• int i;


• float f;


• char str[20];


• };




• int main( )


• {


• union Data data;




• printf( "Memory size occupied by data : %d ", sizeof(data));




• return 0;


• }



21.指针

• #include <stdio.h>




• int main ()


• {


• int var = 20; /* 实际变量的声明 */


• int *ip; /* 指针变量的声明 */




• ip = &var; /* 在指针变量中存储 var 的地址 */




• printf("Address of var variable: %p ", &var );




• /* 在指针变量中存储的地址 */


• printf("Address stored in ip variable: %p ", ip );




• /* 使用指针访问值 */


• printf("Value of *ip variable: %d ", *ip );




• return 0;


• }



22.文件读写

写入文件

• #include <stdio.h>




• int main()


• {


• FILE *fp = NULL;




• fp = fopen("/tmp/test.txt", "w+");


• fprintf(fp, "This is testing for fprintf... ");


• fputs("This is testing for fputs... ", fp);


• fclose(fp);


• }



读取文件

• #include <stdio.h>




• int main()


• {


• FILE *fp = NULL;


• char buff[255];




• fp = fopen("/tmp/test.txt", "r");


• fscanf(fp, "%s", buff);


• printf("1: %s ", buff );




• fgets(buff, 255, (FILE*)fp);


• printf("2: %s ", buff );




• fgets(buff, 255, (FILE*)fp);


• printf("3: %s ", buff );


• fclose(fp);




• }



C语言与C++学习路线

23.排序算法

十大经典排序算法(动态演示+代码)

24.查找算法

九种查找算法

25.面试知识

C语言与C++面试知识总结

26.字符串操作

字符串操作的全面总结

27.C语言常用标准库解读

C语言常用标准库解读

28. C语言最常用的贪心算法

C语言最常用的贪心算法就这么被攻克了

29. 常见的C语言内存错误及对策

常见的C语言内存错误及对策

30. C语言实现面向对象的原理

C语言实现面向对象的原理

31. C语言/C++内存管理

看完这篇你还能不懂C语言/C++内存管理？

32. 再谈C语言指针

再谈指针：大佬给你拨开 C 指针的云雾

C语言函数指针之回调函数

C语言指针详解(文末有福利)

33. C语言预处理命令

长文详解：C语言预处理命令

34. C语言高效编程与代码优化

C语言高效编程与代码优化

35. C语言结构体

C语言之结构体就这样被攻克了！值得收藏！

36. 原码, 反码, 补码 详解

原码, 反码, 补码 详解

37. C语言宏定义

简述C语言宏定义的使用

38. c语言之共用体union、枚举、大小端模式

c语言之共用体union、枚举、大小端模式