【正文】 *取出 num1的最低位 */ reverse=reverse*10+m。 /*將最低位組裝到 reverse中 */ num1=num1/10。 /*去掉 num1的最低位 */ } if (num==reverse) printf(%d 是回文數(shù) \n,num)。 else printf(%d 不是回文數(shù) \n,num)。 system(PAUSE)。 return 0。 } 判斷回文數(shù) 算法 2 82 總結(jié)：循環(huán)結(jié)構(gòu)解題 ? 很多題目都需要循環(huán)結(jié)構(gòu)進(jìn)行求解。 ? 當(dāng)一時(shí)難以整理出每次循環(huán)（迭代）所做的事情時(shí)，可以先看一下如果這件事情交給人做的話，一步一步是怎么做的。 ? 在上一步基礎(chǔ)上抽象出循環(huán)結(jié)構(gòu)的四個(gè)方面。 2 循 環(huán) 條 件3 本 次 循 環(huán) 本 職 工 作1 循 環(huán) 初 始 化4 下 次 循 環(huán) 的 準(zhǔn) 備 工 作 83 總結(jié)：循環(huán)結(jié)構(gòu)解題 2 循 環(huán) 條 件3 本 次 循 環(huán) 本 職 工 作1 循 環(huán) 初 始 化4 下 次 循 環(huán) 的 準(zhǔn) 備 工 作? 2和 3一般沒有絕對的先后順序。 ? 在分析清楚 2和 3后，才分析 4（為什么？）。 ? 一般將 1放在最后分析 在 4中，要對出現(xiàn)在 2和 3中的某些變量進(jìn)行修改，為下次循環(huán)做好準(zhǔn)備，并使得循環(huán)能最終結(jié)束。 思考上述四項(xiàng)工作有無先后順序？應(yīng)該是什么順序？ 84 總結(jié)：對一批數(shù)進(jìn)行處理的模式 n 滿 足 循 環(huán) 條 件處 理 n讀 取 n讀 取 n標(biāo) 記 控 制 的 循 環(huán)循 環(huán) 初 始 化 i = N讀 取 第 i 個(gè) 數(shù) ni = 1處 理 ni = i + 1計(jì) 數(shù) 器 控 制 的 循 環(huán)循 環(huán) 初 始 化循環(huán)次數(shù)未知 循環(huán)次數(shù)已知 85 算法的概念 算法的三種基本結(jié)構(gòu) 算法的描述方法 結(jié)構(gòu)化程序設(shè)計(jì)方法 算法設(shè)計(jì)實(shí)例研究 提綱 86 例 設(shè)計(jì)交通車輛觀測統(tǒng)計(jì)算法。 ? 問題描述：在一個(gè)路口設(shè)置一個(gè)探測器，通過通信線路連接到后臺(tái)的計(jì)算機(jī)。路口每通過一輛汽車，探測器向計(jì)算機(jī)發(fā)出一個(gè)車輛信號(hào) ‘ 1’ ，探測器每隔 1秒鐘向計(jì)算機(jī)發(fā)出一個(gè)時(shí)鐘信號(hào) ‘ 0’ ，觀測結(jié)束向計(jì)算機(jī)發(fā)出結(jié)束信號(hào) ‘ ＃ ’ 。 ? 要求在計(jì)算機(jī)上設(shè)計(jì)一個(gè)程序，能夠接收探測器發(fā)出的信號(hào)，統(tǒng)計(jì)出觀測的時(shí)長、在觀測時(shí)長內(nèi)通過的車輛總數(shù)、以及兩輛車之間最大的時(shí)間間隔。 問題分析：探測器向計(jì)算機(jī)發(fā)出的信號(hào)可以認(rèn)為是一個(gè)任意長的字符序列（以‘ ?結(jié)束），比如：“ 011011000111101”，這樣設(shè)計(jì)程序?qū)嶋H上演變?yōu)樽x取該字符序列，然后進(jìn)行相關(guān)的操作。 ?1? 算法設(shè)計(jì)實(shí)例研究 觀測時(shí)長 ：字符序列中 ?0?的個(gè)數(shù) (6秒 )； 車輛總數(shù) ：字符序列中 ?1?的個(gè)數(shù) (9輛 )； 兩車間最大時(shí)間間隔 ：兩個(gè) ?1?之間的最大連續(xù) ?0?的個(gè)數(shù)(3秒 )； 探測器 87 ? 計(jì)算觀測時(shí)長（ ‘ 0’ 的個(gè)數(shù)）和車輛總數(shù)（ ‘ 1’ 的個(gè)數(shù)）是容易實(shí)現(xiàn)的，但是如何計(jì)算最大時(shí)間間隔需要進(jìn)一步考慮。在對一個(gè)比較復(fù)雜的問題進(jìn)行分析時(shí)，我們應(yīng)該采用分而治之的方法，將復(fù)雜的問題分解為相對比較簡單的問題，再針對該較簡單問題進(jìn)行求解。 ? 我們首先設(shè)計(jì)算法主體框架。 “ 0000110100011010” ！注意： 2022年 9月出版的教材假設(shè)接收到的信號(hào)總是以 ‘ 1’ 開始，因此算法會(huì)有所簡化 88 “ 0000110100011010” 讀 取 第 一 個(gè) 信 號(hào)分 析 設(shè) 計(jì) 說 明 ：此 處 可 以 考 慮 設(shè) 置 變 量 s i g n a l， 代 表 讀 入 的 信 號(hào) 。當(dāng) 信 號(hào) 觀 測 未 結(jié) 束處 理 當(dāng) 前 信 號(hào)讀 取 下 一 個(gè) 信 號(hào)進(jìn) 行 初 始 化 設(shè) 置輸 出 統(tǒng) 計(jì) 結(jié) 果需 輸 出 整 個(gè) 觀 測 時(shí) 長 ， 映 射 為 統(tǒng) 計(jì) ‘ 0 ’ 的 個(gè) 數(shù) ；每 兩 輛 車 之 間 的 最 大 間 隔 時(shí) 長 ；在 觀 測 時(shí) 間 內(nèi) 通 過 的 車 輛 總 數(shù) ， 映 射 為 統(tǒng) 計(jì) ‘ 1 ’的 個(gè) 數(shù) ；1signal!=‘ ’ 待細(xì)化 89 如 果 是 車 輛 信 號(hào)1處 理 車 輛 信 號(hào)YN處 理 時(shí) 鐘 信 號(hào)對 “ 處 理 當(dāng) 前 信 號(hào) ” 進(jìn) 行 細(xì) 化 ，采 用 分 支 結(jié) 構(gòu) 分 別 處 理 車 輛 和 時(shí) 鐘 信 號(hào) 。 90 Level 1層算法設(shè)計(jì) 當(dāng) 信 號(hào) 觀 測 未 結(jié) 束進(jìn) 行 初 始 化 設(shè) 置處 理 當(dāng) 前 信 號(hào)讀 取 下 一 個(gè) 信 號(hào)輸 出 統(tǒng) 計(jì) 結(jié) 果讀 取 第 一 個(gè) 信 號(hào)1 . 1 1 . 21 . 31 . 4當(dāng) 信 號(hào) 觀 測 未 結(jié) 束 : s i g n a l ≠ ‘ ’進(jìn) 行 初 始 化 設(shè) 置 :v e h i c l e s 223。 0 。 s e c o n d s 223。 0 。讀 取 下 一 個(gè) 信 號(hào) s i g n a l輸 出 統(tǒng) 計(jì) 結(jié) 果 : v e h i c l e s 。 s e c o n d s ；及 兩 車 之 間 最 大 間 隔讀 取 第 一 個(gè) 信 號(hào) s i g n a l如 果 是 車 輛 信 號(hào)s i g n a l = ‘ 1 ’處 理 時(shí) 鐘 信 號(hào)NY處 理 車 輛 信 號(hào)第 0層算法 第 1層算法 91 “ 0000110100011010” ? ： 處理時(shí)鐘信號(hào) ‘ 0’ s e c o n d s 223。 s e c o n d s + 1 。v e h i c l e s 0NYi n t e r v a l 223。 i n t e r v a l + 1 。? 觀測時(shí)長 seconds加 1； ? 兩種情況。如果此前已接收到車輛信號(hào) ‘ 1’ (如何判斷？ )，則間隔時(shí)長 interval加 1；否則不做任何處理。 92 “ 0000110100011010” ? ： 處理車輛信號(hào)‘ 1? – 第一種： “ 0000110100011010”（這是第一個(gè)‘ 1?） ?車輛總數(shù) vehicles加 1 – 第二種： “ 0000110100011010”（不是第一個(gè)‘ 1?，且前一個(gè)信號(hào)也是‘ 1? ） ?車輛總數(shù) vehicles加 1 – 第三種： “ 0000110100011010”（不是第一個(gè)‘ 1?，且前一個(gè)信號(hào)是‘ 0? ） ?車輛總數(shù) vehicles加 1 ?處理是否要更新最長時(shí)間間隔（ interval：兩車之間的時(shí)間間隔， longest：兩車之間的最長時(shí)間間隔） 93 “ 0000110100011010” ? 分析：處理車輛信號(hào) ‘ 1’ vehicles＝ vehicles +1； ? 情況 1：第一個(gè)‘ 1? 判斷式： vehicles ==1 ? 情況 2：不是第一個(gè)‘ 1?，且前一個(gè)信號(hào)也是‘ 1? 判斷式： vehicles1 amp。amp。 interval==0 ? 情況 3：不是第一個(gè)‘ 1?，且前一個(gè)信號(hào)是‘ 0? : 判斷式： vehicles1 amp。amp。 interval0 處理： 1）若 intervallongest 則 longest ＝ interval。 2） interval＝ 0。 Yv e h i c l e s 223。 v e h i c l e s + 1 。 i n t e r v a l 223。 0 。 i n t e r v a l l o n g e s tNYl o n g e s t 223。 i n t e r v a lv e h i c l e s ＝ = 1YN i n t e r v a l 0YN情況 1 情況 3 情況 2 94 “ 0000110100011010”驗(yàn)證算法 【 程序演示 】 v e h i c l e s 223。 0 。 s e c o n d s 223。 0 。 l o n g e s t 223。 0 。 i n t e r v a l 223。 0 。讀 取 下 一 個(gè) 信 號(hào) s i g n a l讀 取 第 一 個(gè) 信 號(hào) s i g n a l s i g n a l = = ‘ 1 ’YNW h i l e ( s i g n a l ≠ ‘ ’ )打 印 ( ‘ 觀 測 時(shí) 長 ’ ， s e c o n d s ) ； 打 印 ( ‘ 通 過 車 輛 數(shù) ’ , v e h i c l e s ) 。打 印 ( ‘ 最 大 間 隔 ’ , l o n g e s t ) 。s e c o n d s 223。 s e c o n d s + 1 。v e h i c l e s 0NYi n t e r v a l 223。 i n t e r v a l + 1 。Yv e h i c l e s 223。 v e h i c l e s + 1 。 i n t e r v a l 223。 0 。 i n t e r v a l l o n g e s tNYl o n g e s t 223。 i n t e r v a lv e h i c l e s ＝ = 1YN i n t e r v a l 0YN 95 include main() { int vehicles。 //記錄車輛信號(hào)總數(shù) int seconds。 //記錄時(shí)鐘信號(hào)總數(shù) int longest。 //記錄最長時(shí)間間隔 int interval。 //記錄時(shí)間間隔 char signal。 //存放讀取的信號(hào) /* 初始化設(shè)置 */ vehicles=0。 seconds=0。 longest=0。 interval=0。 printf(please input signal: \n)。 scanf(%c,amp。signal)。 /* 讀入第一個(gè)信號(hào) */ 96 /* 循環(huán)結(jié)構(gòu)處理輸入信號(hào)的字符序列 ,邊讀取邊處理 */ while (signal!=39。39。) { if (signal==39。139。){ /* 處理車輛信號(hào) */ vehicles=vehicles+1。 if (vehicles1 amp。amp。 interval0){ if (intervallongest) longest=interval。 interval=0。 } } else{/* 處理時(shí)鐘信號(hào) */ seconds=seconds+1。 if (vehicles0) interval=interval+1。 }