某知名問答平臺PHP工程師面試筆試真題20

某知名問答平臺PHP工程師面試筆試真題20一、選擇題1.

一張表，里面有ID自增主鍵，當insert了17條記錄之后，刪除了第15，16，17條記錄，再把MySQL重啟，再insert一條記錄，這條記錄的（江南博哥）ID是______A.表類型是MyISAM則ID是18，表類型是InnoDB則ID是15B.表類型是MyISAM則ID是18，表類型是InnoDB則ID是18C.表類型是MyISAM則ID是15，表類型是InnoDB則ID是15D.表類型是MyISAM則ID是17，表類型是InnoDB則ID是15正確答案：A[解析]因為MyISAM表會把自增主鍵的最大ID記錄到數(shù)據(jù)文件中，重啟MySQL自增主鍵的最大ID也不會丟失。所以，插入后的ID值為18。而InnoDB表只是把自增逐漸的最大ID記錄到內(nèi)存中，重啟MySQL或?qū)Ρ磉M行OPTIMIZE操作，都會導致最大ID丟失。所以，插入后ID的值為15。

所以，本題的答案為A。

2.

下面語句執(zhí)行的結(jié)果是______

＜?php

$i=0;

echo++$i;

echo$i++;

$a=++$i;

echo$a++;

$i=$a;

echo$i;

?＞A.1234B.1134C.1233D.1235E.以上都不是正確答案：B[解析]$i的值為0，++$i的意思是$i加1后把值給$i，所以$i的值輸出得到1，然后$i++表示先得到$i的值然后加1，所以輸出得到1，$i加1，$i的值變?yōu)?。在執(zhí)行$a=++$i時，它等價于$a=2+1，因此$a值為3。對應地輸出$a++時，先輸出3，然后加1，所以輸出后的$a的值變?yōu)?，然后把4賦值給$i，$i輸出得到4。最終結(jié)果得到1134。選項B正確。

所以，本題的答案為B。

3.

$result=preg_replace("∧s*\[quote\][\n\r]*(.+?)[\n\r]*\[∨quote\]\s*/is","\\1",$str);該語句會匹配和替換出什么樣的$str?______A.[quote][/quote]不區(qū)分大小寫B(tài).[quote][/quote]區(qū)分大小寫C.如果$str="[quote]\t\nabc\t\n[/quote]，那么$result="\t\nabc\t\n";D.如果$str="[quote]\t\nabc\t\n[/quote]，那么$result='abc';正確答案：AD[解析]preg_replace()函數(shù)正則匹配時不區(qū)分字符串的大小進行匹配。選項A正確，選項B錯誤。

對于選項CD相同的字符串，通過正則匹配后獲得的$result值為abc。選項D正確，選項C錯誤。

所以，本題的答案為AD。

4.

用stream_get_meta_data函數(shù)，流API無法提供______A.是否仍然有數(shù)據(jù)未讀B.流是否過期C.流是否被阻擋D.通過流傳輸了多少數(shù)據(jù)E.流構(gòu)建的成分正確答案：D[解析]stream_get_meta_data函數(shù)可以獲取是否仍然有數(shù)據(jù)未讀、流是否過期、流是否被阻擋、流構(gòu)建的成分等信息，但是無法顯示通過流傳輸了多少數(shù)據(jù)，只能顯示還剩多少數(shù)據(jù)需要傳輸。選項D正確。

所以，本題的答案為D。

5.

考慮如下腳本，最后文件myfile.txt的內(nèi)容是______

＜?php

$array='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

$f=fopen("myfile.txt","r");

for($i=0;$i＜50;$i++){

fwrite($f.$array[rand(0,strlen($atray)-1)]);

}

?＞A.什么都沒有，因為$array實際上是一個字符串，而不是數(shù)組B.49個隨機字符C.50個隨機字符D.41個隨機字符E.什么都沒有，或者文件不存在，腳本輸出一個錯誤正確答案：E[解析]本題中，文件被以r模式打開，即只讀模式。因此，如果文件不存在，那么PHP將輸出一個錯誤來指出沒有找到文件。如果文件存在，那么fopen()將被成功調(diào)用，但由于是以只讀方式打開，fwrite()會失敗。如果用w代替r，那么腳本就能正常運行，并且myfile.txt內(nèi)將有50個隨機字符(記住，可以像訪問數(shù)組那樣使用索引來訪問字符串)。

所以，本題的答案為E。

6.

error_reporting(2047)的作用是______A.顯示致命的運行錯誤B.顯示全部的運行錯誤C.隱藏全部運行錯誤D.顯示警告、非致命性錯誤正確答案：B[解析]2047=1+2+4+8+16+32+64+128+256+512+1024。其中，1對應E_ERROR，2對應E_WARNING，4對應E_PARSE，8對應E_NOTICE，16對應E_CORE_ERROR，32對應E_CORE_WARNING，64對應E_COMPILE_ERROR，128對應E_COMPILE_WARNING，256對應E_USER_ERROR，512對應E_USER_WARNING，1024對應E_USER_NOTICE。

綜上分析，error_reporting(2047)表示上述錯誤都會顯示出來。

所以，本題的答案為B。

7.

假設瀏覽器沒有重啟，那么在最后一次訪問后的多久，會話(Session)才會過期并被回收?______A.1440s后B.在session.gc_maxlifetime設置的時間過了后C.除非手動刪除，否則永不過期D.除非瀏覽器重啟，否則永不過期E.以上都不對正確答案：B[解析]session.gc_maxlifetime設置的是用戶最后一次請求到Session被回收之間的時間間隔。

盡管數(shù)據(jù)文件并沒有被真正刪除，不過一旦Session被回收，將無法對此Session進行訪問。巧合的是，session.gc_maxlifetime的默認設置正好是1440s，但這個數(shù)字是可以被系統(tǒng)管理員調(diào)整的。

所以，本題的答案為B。

8.

以下方法中，能保證鎖在任何競爭情況下都安全的是______A.用flock()鎖住指定文件B.用fopen()在系統(tǒng)的臨時文件夾里打開文件C.用tempnam()創(chuàng)建一個臨時文件D.用mkdir()創(chuàng)建一個臨時文件夾E.用tmpfile()創(chuàng)建一個臨時文件正確答案：D[解析]對于選項A，flock()函數(shù)使用的是協(xié)議鎖定機制，即所有其他訪問此文件的線程必須使用flock()，如果某個線程沒有這么做，那么就會產(chǎn)生競爭，鎖就不安全了。選項A錯誤。

對于選項B，使用fopen()打開的臨時文件不能保證文件鎖的安全，一樣會產(chǎn)生競爭。

對于選項C和選項E創(chuàng)建的臨時文件也不能保證不存在競爭。

對于選項D，用mkdir創(chuàng)建一個文件夾能保證任何時刻只有一個進程能處理這個文件夾，即保證操作的原子性。因此，在多線程編程的時候，也可以使用這個特性來達到多線程安全的目的。具體實現(xiàn)方法：多線程可以通過創(chuàng)建一個相同的臨時文件夾來實現(xiàn)多線程的同步，操作結(jié)束后再刪除這個文件夾。在此過程中，一旦其中一個線程創(chuàng)建成功了這個臨時文件夾，其他線程將無法創(chuàng)建同名的文件夾。在這種情況下，其他線程只能等待這個臨時文件夾被刪除后才能繼續(xù)往下執(zhí)行，直到I/O操作完成。選項D正確。

所以，本題的答案為D。

9.

以下有關PHP面向?qū)ο蟮恼f法中，不正確的是______A.如果PHP的子類中定義了構(gòu)造函數(shù)，那么創(chuàng)建子類的對象時，會隱式地調(diào)用其父類的構(gòu)造函數(shù)B.序列化一個對象將會保存對象的所有變量，但是不會保存對象的方法，只會保存類的名字C.類名可以是任何非PHP保留字的合法標簽，漢字也可以作為PHP的類名D.要實現(xiàn)一個接口，使用implements操作符，類中必須實現(xiàn)接口中定義的所有方法，否則會報一個致命錯誤正確答案：A[解析]當子類和父類中都存在構(gòu)造函數(shù)時，子類中的構(gòu)造函數(shù)會覆蓋父類的構(gòu)造函數(shù)，當實例化子類時，會自動調(diào)用子類的構(gòu)造函數(shù)。選項A正確。

所以，本題的答案為A。

10.

PHP以CGI的形式運行在Linux+Apache系統(tǒng)的cgi-bin文件夾中。如果有人打開以下URL，那么將發(fā)生什么?/cgi-bin/php?/etc/passwd。______A./etc/passwd目錄下的文件都會被顯示出來，造成安全隱患B.操作系統(tǒng)會檢查Apache是否允許打開/etc/passwd目錄C./etc/passwd字符串作為參數(shù)傳給了腳本D.什么都不會發(fā)生。CGI模式下的PHP將自動拒絕此次訪問E.PHP嘗試把/etc/passwd作為PHP腳本進行解釋正確答案：D[解析]對于選項A，因為PHP以CGI模式運行，所以為了安全，PHP會采取一些措施來減少常見的安全隱患。選項A錯誤。

PHP中的安全措施是應用在把任意某個文件作為命令行參量傳遞給解釋器執(zhí)行的時候。如果不是執(zhí)行這個措施，那么PHP將嘗試讀取/etc/passwd——一個“全球可讀(world-readable)”的文件，同時解釋器把它視作PHP腳本來執(zhí)行，最終導致所有的用戶賬號被輸出到客戶端上。因為PHP內(nèi)建的安全機制，所以頁面是不會有內(nèi)容輸出的。選項D正確，選項B選項C選項E錯誤。

所以，本題的答案為D。

二、填空題1.

Mysql服務器默認端口是______。正確答案：3306。

2.

請寫出10個Linux常用的命令______、______、______、______、______、______、______、______、______、______。正確答案：ls、mkdir、cp、mv、find、pwd、vim、rm、touch、cd。[解析]1)ls的作用是查詢目錄的內(nèi)容，格式為ls[選項][文件或目錄]。

2)mkdir的作用是建立目錄，格式為mkdir-p[目錄名]。

3)cp的作用是復制文件或目錄，格式為cp[選項][原文件目錄][目標目錄]。

4)mv的作用是文件剪切、改名，格式為mv[原文件目錄][目標文件目錄]。

5)find的作用是搜索文件、目錄，格式為mv[原文件目錄][目標文件目錄]。

6)pwd的作用是顯示當前所在工作目錄的全路徑，格式為pwd[選項]。

7)vim的作用是編輯文件，格式為vim[文件]進入文件或者創(chuàng)建文件(文件不存在的情況下)。

8)rm的作用是刪除文件或目錄，格式為rm[文件]。

9)touch的作用是創(chuàng)建文件和修改文件，格式為touch[選項][文件名或者目錄名]。

10)cd的作用是切換目錄，格式為cd[目錄]。

3.

Mysql中的鎖可劃分為______、______。正確答案：表鎖、行級鎖。[解析]表鎖是MySQL中最基本的鎖策略，并且是開銷最小的策略?？梢灾苯渔i定整張表，在鎖定期間可以同時讀，但是不能寫入。

行級鎖可以最大限度地支持并發(fā)處理(同時帶來了最大的鎖開銷)。只對指定的記錄進行鎖定，可以保證對同一張表的讀和寫入。

4.

Redis支持的數(shù)據(jù)類型有______、______、______、______、______。正確答案：string(字符串)、list(列表)、set(集合)、zset(有序集合)和hash(哈希類型)。[解析]Redis是一個key-value存儲系統(tǒng)。和Memcached類似，它支持存儲的value類型相對更多，包括string(字符串)、list(鏈表)、set(集合)、zset(sortedset，有序集合)和hash(哈希類型)。

5.

Memcache能接受的key的最大長度是______。正確答案：250個字符。[解析]Memcache要求key的最大長度是250個字符，如果使用的客戶端支持“key”的前綴，那么key可以是前綴+原始key，最大長度可以超過250個字符。但是為了節(jié)省內(nèi)存和帶寬，不建議使用太長字符做key。

三、簡答題1.

一、二、三、四范式有何區(qū)別?正確答案：在設計與操作維護數(shù)據(jù)庫時，最關鍵的問題就是要確保數(shù)據(jù)正確地分布到數(shù)據(jù)庫的表中，使用正確的數(shù)據(jù)結(jié)構(gòu)，不僅有助于對數(shù)據(jù)庫進行相應的存取操作，還可以極大地簡化應用程序的其他內(nèi)容(查詢、窗體、報表、代碼等)，正確地進行表的設計稱為“數(shù)據(jù)庫規(guī)范化”，它的目的就是減少數(shù)據(jù)庫中的數(shù)據(jù)冗余，從而增加數(shù)據(jù)的一致性。

范化是在識別數(shù)據(jù)庫中的數(shù)據(jù)元素、關系，以及定義所需的表和各表中的項目這些初始工作之后的一個細化的過程。常見的范式有1NF、2NF、3NF、BCNF以及4NF。

1NF，第一范式。是指數(shù)據(jù)庫表的每一列都是不可分割的基本數(shù)據(jù)項，同一列中不能有多個值，即實體中的某個屬性不能有多個值或者不能有重復的屬性。如果出現(xiàn)重復的屬性，那么就可能需要定義一個新的實體，新的實體由重復的屬性構(gòu)成，新實體與原實體之間為一對多關系。第一范式的模式要求屬性值不可再分裂成更小部分，即屬性項不能是屬性組合或由組屬性組成。簡而言之，第一范式就是無重復的列。例如，由“職工號”“姓名”“電話號碼”組成的表(一個人可能有一個辦公電話和一個移動電話)，這時將其規(guī)范化化為1NF可以將電話號碼分為“辦公電話”和移動電話兩個屬性，即職工(職工號，姓名，辦公電話，移動電話)。

2NF，第二范式。第二范式(2NF)是在第一范式(1NF)的基礎上建立起來的，即滿足第二范式(2NF)必須先滿足第一范式(1NF)。第二范式(2NF)要求數(shù)據(jù)庫表中的每個實例或行必須可以被唯一地區(qū)分。為實現(xiàn)區(qū)分通常需要為表加上一個列，以存儲各個實例的唯一標識。如果關系模式R為第一范式，并且R中每一個非主屬性完全函數(shù)依賴于R的某個候選鍵，則稱R為第二范式模式。(如果A是關系模式R的候選鍵的一個屬性，則稱A是R的主屬性，否則稱A是R的非主屬性。)例如，在選課關系表(學號，課程號，成績，學分)中，關鍵字為組合關鍵字(學號，課程號)，但由于非主屬性學分僅依賴于課程號，對關鍵字(學號，課程號)只是部分依賴，而不是完全依賴，所以此種方式會導致數(shù)據(jù)冗余以及更新異常等問題，解決辦法是將其分為兩個關系模式：學生表(學號，課程號，分數(shù))和課程表(課程號，學分)，新關系通過學生表中的外關鍵字課程號聯(lián)系，在需要時進行連接。

3NF，第三范式。如果關系模式R是第二范式，且每個非主屬性都不傳遞依賴于R的候選鍵，則稱R是第三范式的模式。例如，學生表(學號，姓名，課程號，成績)，其中學生姓名無重名，所以該表有兩個候選碼(學號，課程號)和(姓名，課程號)，則存在函數(shù)依賴：學號→姓名，(學號，課程號)→成績，(姓名，課程號)→成績，唯一的非主屬性成績對碼不存在部分依賴，也不存在傳遞依賴，所以屬于第三范式。

BCNF。它構(gòu)建在第三范式的基礎上，如果關系模式R是第一范式，且每個屬性都不傳遞依賴于R的候選鍵，那么稱R為BCNF的模式。假設倉庫管理關系表(倉庫號，存儲物品號，管理員號，數(shù)量)，滿足一個管理員只在一個倉庫工作；一個倉庫可以存儲多種物品。則存在如下關系：

(倉庫號，存儲物品號)→(管理員號，數(shù)量)

(管理員號，存儲物品號)→(倉庫號，數(shù)量)

所以，(倉庫號，存儲物品號)和(管理員號，存儲物品號)都是倉庫管理關系表的候選碼，表中的唯一非關鍵字段為數(shù)量，它是符合第三范式的。但是，由于存在如下決定關系：

(倉庫號)→(管理員號)

(管理員號)→(倉庫號)

即存在關鍵字段決定關鍵字段的情況，所以其不符合BCNF范式。把倉庫管理關系表分解為兩個關系表：倉庫管理表(倉庫號，管理員號)和倉庫表(倉庫號，存儲物品號，數(shù)量)，這樣的數(shù)據(jù)庫表是符合BCNF范式的，消除了刪除異常、插入異常和更新異常。

4NF，第四范式。設R是一個關系模式，D是R上的多值依賴集合。如果D中成立非平凡多值依賴X—Y時，X必是R的超鍵，那么稱R是第四范式的模式。例如，職工表(職工編號，職工孩子姓名，職工選修課程)，在這個表中同一個職工也可能會有多個職工孩子姓名，同樣，同一個職工也可能會有多個職工選修課程，即這里存在著多值事實，不符合第四范式。如果要符合第四范式，那么只需要將上表分為兩個表，使它們只有一個多值事實，例如，職工表一(職工編號，職工孩子姓名)，職工表二(職工編號，職工選修課程)，兩個表都只有一個多值事實，所以符合第四范式。

下圖為各范式關系圖。

2.

如果數(shù)據(jù)庫日志滿了，那么會出現(xiàn)什么情況?正確答案：日志文件(LogFile)記錄所有對數(shù)據(jù)庫數(shù)據(jù)的修改，主要是保護數(shù)據(jù)庫以防止故障，以及恢復數(shù)據(jù)時使用。其特點如下：

1)每一個數(shù)據(jù)庫至少包含兩個日志文件組。每個日志文件組至少包含兩個日志文件成員。

2)日志文件組以循環(huán)方式進行寫操作。

3)每一個日志文件成員對應一個物理文件。

通過日志文件來記錄數(shù)據(jù)庫事務可以最大限度地保證數(shù)據(jù)的一致性與安全性，但一旦數(shù)據(jù)庫中日志滿了，就只能執(zhí)行查詢等讀操作，不能執(zhí)行更改、備份等操作，原因是任何寫操作都要記錄日志，也就是說，基本上處于不能使用的狀態(tài)。

3.

請簡要描述你對Memcache的理解，它的優(yōu)點有哪些?正確答案：Memcache是一個高性能的分布式內(nèi)存對象緩存系統(tǒng)，主要通過在內(nèi)存里維護一個巨大的hash表進行數(shù)據(jù)緩存。它主要是將數(shù)據(jù)調(diào)用到內(nèi)存中，然后從內(nèi)存中讀取數(shù)據(jù)，從而提高讀取熟讀。它主要通過key-value的形式存儲各種數(shù)據(jù)，包括圖像、視頻、文件等。

它具有以下優(yōu)點：

1)支持多臺服務器使用Memcache。由于Memcache的存儲數(shù)據(jù)大小必須小于內(nèi)存的大小，所以可以將Memcache使用在多臺服務器上，增加緩存容量。

2)支持均衡請求。當使用多臺Memcache服務器時，可以均衡請求，避免所有請求都進入一臺Memcache服務器中，導致服務器掛掉。

3)支持分布式?？梢越鉀Q緩存本身水平線性擴展的問題和緩存大并發(fā)下的本身性能問題，避免緩存的單點故障問題。

4)支持部分容災問題。即如果多臺服務器存儲了Memcache數(shù)據(jù)，那么其中一臺Memcache服務器掛掉，部分請求還是可以在Memcache中命中，為修復掛掉的服務器爭取一些時間。

4.

如何預防SOL注入攻擊?正確答案：所謂SQL注入式攻擊，就是攻擊者把SQL命令插入Web表單的域或頁面請求的查詢字符串中，欺騙服務器執(zhí)行惡意的SQL命令。在某些表單中，用戶輸入的內(nèi)容直接用來構(gòu)造動態(tài)SQL命令，或作為存儲過程的輸入?yún)?shù)，這類表單特別容易受到SQL注入式攻擊。例如，對于一個站點/News/details.jsp?id=2的頁面，id是查詢參數(shù)，通過id獲取顯示某條信息，在JSP程序中，用SQL語句來讀取該條新聞："select*fromnewswhereid="+id，正常執(zhí)行的話，只需要將id替換為參數(shù)2即可，沒有任何問題，但是當非法用戶將id的參數(shù)變?yōu)閕d=2;dropdatabasenews時，則執(zhí)行的SQL語句除了讀取對應的新聞信息外，還會執(zhí)行dropdatabasenews信息，可是后面這條語句是非法的。

由于SQL注入攻擊利用的是合法的SQL語句，使得這種攻擊不能被防火墻檢查，而且由于對任何基于SQL語言標準的數(shù)據(jù)庫都適用，所以危害特別大。盡管如此，目前防止SQL注入攻擊的方法也非常多，下面介紹常用的一些方法：

1)預處理語句和參數(shù)分別發(fā)送到數(shù)據(jù)庫服務器進行解析。

2)使用函數(shù)addslashes()轉(zhuǎn)義提交的內(nèi)容。

3)PHP配置文件中開啟magic_quotes_gpc=on；將自動轉(zhuǎn)換用戶查詢的SQL語句，對防止SQL注入有重大作用。

4)在PHP配置文件中，將register_globals設置為off，關閉全局變量注冊。

5)在PHP配置文件中，開啟安全模式safe_mode=on;。

6)SQL語句的書寫盡量不要省略單引號。

7)提高數(shù)據(jù)庫表和字段的命名技巧，對一些重要的字段根據(jù)程序的特點命名，取不易被猜到的名字。

8)控制錯誤信息，關閉錯誤信息的輸出，將錯誤信息寫到日志文件中，不要在網(wǎng)站暴露錯誤信息。

5.

抓取遠程圖片到本地，會用到什么函數(shù)?這些函數(shù)有什么作用?正確答案：fsockopen、fread、fwrite和fclose。由于需要抓取遠程圖片，因此需要使用fsocketopen來打開一個網(wǎng)絡連接，然后可以通過這個網(wǎng)絡連接(打開的地址為這個網(wǎng)絡上的圖片地址)，打開成功后會返回一個文件句柄，然后可以使用fread函數(shù)讀取文件內(nèi)容，使用fwrite函數(shù)把文件內(nèi)容寫到本地(實現(xiàn)了把遠程圖片抓取到本地的功能)，最后使用fclose關閉這個連接。

四、編程題1.

給定一個大小為n×n的迷宮，一只老鼠需要從迷宮的左上角(對應矩陣的[0][0])走到迷宮的右下角(對應矩陣的[1][N-1])，老鼠只能向兩方向移動：向右或向下。在迷宮中，0表示沒有路(是死胡同)，1表示有路。例如，給定下面的迷宮。1000110101001111

圖中標粗的路徑就是一條合理的路徑。請給出算法來找到這條合理路徑。正確答案：最容易想到的方法就是嘗試所有可能的路徑，找出可達的一條路。顯然這種方法效率非常低下，這里重點介紹一種效率更高的回溯法。主要思路：當碰到死胡同的時候，回溯到前一步，然后從前一步出發(fā)繼續(xù)尋找可達的路徑。算法的主要框架如下：

1)申請一個結(jié)果矩陣來標記移動的路徑。

if到達了目的地

打印解決方案矩陣

else

2)在結(jié)果矩陣中標記當前為1(1表示移動的路徑)。

3)向右前進一步，然后遞歸地檢查，走完這一步后，是否存在到終點的可達的路線。

4)如果步驟2)中的移動方法導致沒有通往終點的路徑，那么選擇向下移動一步，然后檢查使用這種移動方法后，是否存在到終點的可達的路線。

5)如果上面的移動方法都會導致沒有可達的路徑，那么標記當前單元格在結(jié)果矩陣中為0，返回false，并回溯到前一步中。

根據(jù)以上框架很容易進行代碼實現(xiàn)了。示例代碼如下：

＜?php

define("N",4);

/*打印最終結(jié)果*/

functionprintSolution(&$sol)

{

for($i=0;$i＜N;$i++)

{

for($j=0;$j＜N;$j++)

printf("%d",$sol[$i][$j]);

printf("＜br＞");

}

}

/*判斷x,y是不是合理的可走的單元*/

functionisSafe($maze,$x,$y)

{

if($x＞=0&&$x＜N&&$y＞=0&&$y＜N&&$maze[$x][$y]==1)

returntrue;

else

returnfalse;

}

functiongetPath($maze,$x,$y,&$sol)

{

/*走到了目的地*/

if($x==N-1&&$y==N-1)

{

$sol[$x][$y]=1;

returntrue;

}

/*檢查maze[x][y]是否是合理可走的單元*/

if(isSafe($maze,$x,$y))

{

/*標記當前的單元為1*/

$sol[$x][$y]=1;

/*向右走一步并判斷是否能走到終點*/

if(getPath($maze,$x+1,$y,$sol))

returntrue;

/*向下走一步并判斷是否能走到終點*/

if(getPath($maze,$x,$y+1,$sol))

returntrue;

/*如果上面兩步都不能走到終點，回溯到上一步*/

$sol[$x][$y]=0;

returnfalse;

}

returnfalse；

}

$maze=[

[1,0,0,0],

[1,1,0,1],

[0,1,0,0],

[1,1,1,1]

];

$sol=[

[0,0,0,0],

[0,0,0,0],

[0,0,0,0],

[0,0,0,0]

];

if(!getPath($maze,0,0,$sol))

{

printf("Solutiondoesn'texist");

}

else

{

printSolution($sol);

}

?＞

程序的運行結(jié)果為

1000

1100

0100

0111

2.

坐標軸上從左到右依次的點為a[0]、a[1]、a[2]、…、a[n-1]，設一根木棒的長度為L，求L最多能覆蓋坐標軸的幾個點?正確答案：本題求滿足a[j]-a[i]≤L和a[j+1]-a[i]＞L這兩個條件的j與i之間所包含的點個數(shù)的最大值，即j-i+1最大，這樣題目就簡單多了，方法也很簡單：直接從左到右掃描，使用兩個索引i和j，i從位置0開始，j從位置1開始，如果a[j]-a[i]≤L，則j++前進，并記錄中間經(jīng)過的點的個數(shù)，如果a[j]-a[i]＞L，則j--回退，覆蓋點個數(shù)-1，回到剛好滿足條件的時候，將滿足條件的最大值與前面找出的最大值比較，記錄下當前的最大值，然后執(zhí)行i++、j++，直到求出最大的點個數(shù)。

有兩點需要注意：

1)這里可能不存在i和j使得a[j]-a[i]剛好等于L的情況發(fā)生，所以，判斷條件不能為a[j]-a[i]==L。

2)可能存在不同的覆蓋點但覆蓋的長度相同的情況發(fā)生，此時只選取第一次覆蓋的點。

實現(xiàn)代碼如下：

＜?php