貪心演算法總結

Ⅰ 活動安排問題，貪心演算法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、枚舉、大小端模式