1.2 程序和程序邏輯

學習目標

1）掌握算法與程序的概念。

2）了解算法的基本描述方法。

實例3 程序與算法的概念——梵塔推理

實例任務

將1號柱大小不等的三個物體，移動到3號柱上，順序必須與1號柱順序一致。要求每次只移動一個物體，而且每根柱上小塊物體必須置于大塊物體之上。其移動過程如圖1-10所示。

相關知識

1.程序

程序包括兩部分，一是對數據的描述，即數據結構；二是對操作的描述，即操作步驟，也稱為算法，它指明了解決某一具體問題的方法和步驟。因此，計算機科學家Nikiklaus Wirth提出了如下公式：

數據結構+算法=程序

就算法而言，大致可分為兩大類：一類是數值運算算法，用于求解數值；另一類是非數值運算算法，用于分析推理和邏輯推理。如實例中的梵塔推理并非求解一定的數值，而只是完成一定的推理操作。

2.算法的自然語言描述

實例為梵塔推理難題的解題步驟，也是人邏輯思維的基本方法。計算機的算法思想與此類似，只是表示方法不同而已。

用計算機解此題的難點在于，如何用數據結構表示每塊物體的所在位置，以及如何描述某一物體由1號柱移動到2號柱這一動作，這也是算法設計的關鍵所在。梵塔推理可以用自然語言表示如下：

將A由1號柱移到3號柱mov(A:1,3 )

將B由1號柱移到2號柱mov(B:1,2 )

將A由3號柱移到2號柱mov(A:3,2 )

將C由1號柱移到3號柱mov(C:1,3 )

將A由2號柱移到1號柱mov(A:2,1 )

將B由2號柱移到3號柱mov(B:2,3 )

將A由1號柱移到3號柱mov(A:1,3 )

實例4 算法圖形描述——求n!

實例任務

數學上，階乘n!=1×2×3×…×n。現要求輸入n的值，求出n!的值。程序的運行結果如圖1-11所示。

程序代碼

相關知識

1.N-S圖

流程圖除用自然語言描述外，還可以使用圖形來描述，常用的流程圖有傳統流程圖和N-S圖。N-S圖又稱為結構化盒圖，它使用一種方框來描述程序的基本結構。本實例程序可繪制成如圖1-12所示的N-S圖。

2.傳統流程圖

傳統流程圖是通過指定的幾何圖形框和箭頭線來描述各個環節的操作和執行的過程。這種描述方法比較直觀，而且程序走向清晰，非常易于讀者理解，易于編寫C語言代碼。但如果程序比較復雜，則使用傳統流程圖描述比較煩冗，不易理解。本實例程序可繪制成如圖1-13所示的傳統流程圖。

在傳統流程圖中，長方形框表示執行一定的操作，如賦值或計算等；菱形框表示條件判斷；橢圓矩形框表示程序的開始與結束；平行四邊形表示輸入輸出數據；箭頭表示程序語句的執行方向。

課堂精練

1）用N-S圖描述1+2+3+…+10的值的算法。請將圖1-14中的空缺語句補充完整。

2）用傳統流程圖描述1+2+3+…+10的值的算法。請將圖1-15中的空缺語句補充完整。