基本算法思想之遞推

分治算法的基本思想是將一個計算復雜的問題分為規(guī)模較小偏竟,計算簡單的小問題求解煮落,然后綜合各個小問題,而得到最終問題的答案踊谋。分治算法的執(zhí)行過程如下:

  1. 對于一個規(guī)模為N的問題蝉仇,若該問題可以容易地解決(比如說規(guī)模N較小)殖蚕,則直接解決轿衔,否則執(zhí)行下面的步驟。
  2. 將該分解為M個規(guī)模較小的子問題睦疫,這些子問題互相獨立害驹,并且與原問題形式相同。
  3. 遞歸地解決這些子問題蛤育。
  4. 然后裙秋,將各個子問題的解合并得到原問題的解。
    使用分治算法需要待求解問題能夠化簡為若干個小規(guī)模的相同問題缨伊,通過逐步劃分摘刑,能夠達到一個易于求解的階段而直接進行求解。然后刻坊,程序中可以使用遞歸算法來進行求解枷恕。

下面我們通過一個例子來看分治算法具體的應用場景。

一個袋子里有30個硬幣谭胚,其中一枚是假幣徐块,并且假幣和真幣一模一樣,肉眼很難分辨灾而,目前只知道假幣比真幣輕一點胡控。請問如何區(qū)分出假幣呢?

下面我們來分析一下問題旁趟≈缂ぃ可以采用遞歸分治的思想來求解這個問題,操作步驟如下:

  • 首先為每個硬幣編號,然后可以將所有的硬幣分為兩份橙困,放在天平的兩邊瞧掺。這樣就將區(qū)分30個硬幣的問題,變?yōu)閰^(qū)分兩堆硬幣的問題凡傅。
  • 因為假硬幣的分量較輕辟狈,因此天平較輕一側(cè)中一定包含假硬幣。
  • 再將較輕一側(cè)中的硬幣等分為兩份夏跷,重復上述做法哼转。
  • 直到剩下的兩枚硬幣可用天平直接找出來假硬幣來。
public class Solution {
    static final int MAXNUM = 30;

    public static int FalseCoin(int[] coin, int low, int high) {
        int res = 0;
        int i, sum1, sum2, sum3;
        sum1 = sum2 = sum3 = 0;

        if (low + 1 == high) {
            if (coin[low] < coin[high]) {
                res = low + 1;
                return res;
            } else {
                res = high + 1;
                return res;
            }
        }
        if ((high - low + 1) % 2 == 0) { // n是偶數(shù)
            for(i = low; i <= low + (high - low) / 2; ++i) {
                sum1 = sum1 + coin[i]; // 前半段和
            }
            for (i = low + (high - low) / 2 + 1; i <= high; ++i) {
                sum2 = sum2 + coin[i]; // 后半段和
            }
            if (sum1 > sum2) {
                res = FalseCoin(coin, low + (high - low) / 2 + 1, high);
            }
            else if (sum1 < sum2) {
                res = FalseCoin(coin, low, low + (high - low) / 2);
            } else {

            }
        } else { // n是奇數(shù)
            for (i = low; i <= low + (high - low) / 2 - 1; ++i) {
                sum1 = sum1 + coin[i]; // 前半段和
            }
            for (i = low + (high - low) / 2 + 1; i <= high; ++i) {
                sum2 = sum2 + coin[i]; // 后半段和
            }
            sum3 = coin[low + (high - low) / 2];
            if (sum1 > sum2) {
                res = FalseCoin(coin, low + (high - low) / 2 + 1, high);
                return res;
            } else if (sum1 < sum2) {
                res = FalseCoin(coin, low, low + (high - low) / 2 - 1);
                return res;
            } else {

            }
            if (sum1 + sum3 == sum2 + sum3) {
                res = low + (high - low) / 2 + 1;
                return res;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[] coin = new int[MAXNUM];
        int i, n;
        int pos;
        System.out.println("分治算法求解假硬幣問題槽华!");
        System.out.print("請輸入硬幣總的個數(shù):");
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        System.out.println("請輸入硬幣的真假:");
        for (i = 0; i < n; ++i) {
            coin[i] = in.nextInt();
        }
        pos = FalseCoin(coin, 0, n - 1);
        System.out.println("在上述" + MAXNUM + "個硬幣中释簿,第" + pos + "個硬幣是假的!");
    }
}

遞推算法是一種理性思維模式的代表硼莽,其根據(jù)已有的數(shù)據(jù)和關系,逐步推導而得到結(jié)果煮纵。遞推算法的執(zhí)行過程如下:

  • 根據(jù)已知結(jié)果和關系懂鸵,求解中間結(jié)果。
  • 判斷是否達到要求行疏,如果沒有達到匆光,則繼續(xù)根據(jù)已知結(jié)果和關系求解中間結(jié)果;如果滿足要求酿联,則表示尋找到一個正確的答案终息。

遞推算法往往需要用戶知道答案和問題之間的邏輯。在許多數(shù)學問題中贞让,都有著明確的計算公式可以遵循周崭,因為往往可以采用遞推算法來實現(xiàn)。

下面通過一個斐波那契數(shù)列來看一下遞推的具體應用場景:

如果有一對兩個月大的兔子以后每一個月都可以生一對小兔子喳张,而一對新生的兔子出生兩個月后才可以生小兔子续镇。也就是說,1月份出生销部,3月份才可以產(chǎn)仔摸航。那么假定一年內(nèi)沒有兔子死亡事件,那么1年后共有多少對兔子呢舅桩?

我們先來分析一下兔子產(chǎn)仔問題酱虎。來逐月看一次每月的兔子對數(shù):
第一個月:1對兔子;
第二個月:1對兔子擂涛;
第三個月:2對兔子读串;
第四個月:3對兔子;
第五個月:5對兔子;
......
從上面可以看出爹土,從第3個月開始甥雕,每一個月的兔子總對數(shù)等于前兩個月兔子數(shù)的總和。相應的計算公式如下:
第n個月兔子總數(shù)Fn = Fn-1 + Fn-2胀茵。
這里社露,初始第一個月的兔子數(shù)為:F1 = 1,第二個月的兔子數(shù)為F2 = 1琼娘。

import java.util.Scanner;

public class Solution {

    public static int fibonacci(int n) {
        int t1, t2;
        if (n == 1 || n == 2) {
            return 1;
        } else {
            t1 = fibonacci(n - 1);
            t2 = fibonacci(n - 2);
            return t1 + t2;
        }
    }


    public static void main(String[] args) {
        System.out.println("遞推算法求解兔子產(chǎn)仔問題峭弟!");
        System.out.println("請先輸入時間:");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int num = fibonacci(n);
        System.out.println("經(jīng)過" + n + "月的時間,共能繁殖成" + num + "對兔子脱拼!");
    }
}
運行結(jié)果
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末瞒瘸,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子熄浓,更是在濱河造成了極大的恐慌情臭,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,042評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件赌蔑,死亡現(xiàn)場離奇詭異俯在,居然都是意外死亡,警方通過查閱死者的電腦和手機娃惯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,996評論 2 384
  • 文/潘曉璐 我一進店門跷乐,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人趾浅,你說我怎么就攤上這事愕提。” “怎么了皿哨?”我有些...
    開封第一講書人閱讀 156,674評論 0 345
  • 文/不壞的土叔 我叫張陵浅侨,是天一觀的道長。 經(jīng)常有香客問我证膨,道長仗颈,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,340評論 1 283
  • 正文 為了忘掉前任椎例,我火速辦了婚禮挨决,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘订歪。我一直安慰自己脖祈,他們只是感情好,可當我...
    茶點故事閱讀 65,404評論 5 384
  • 文/花漫 我一把揭開白布刷晋。 她就那樣靜靜地躺著盖高,像睡著了一般慎陵。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上喻奥,一...
    開封第一講書人閱讀 49,749評論 1 289
  • 那天席纽,我揣著相機與錄音,去河邊找鬼撞蚕。 笑死润梯,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的甥厦。 我是一名探鬼主播纺铭,決...
    沈念sama閱讀 38,902評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼刀疙!你這毒婦竟也來了舶赔?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,662評論 0 266
  • 序言:老撾萬榮一對情侶失蹤谦秧,失蹤者是張志新(化名)和其女友劉穎竟纳,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體疚鲤,經(jīng)...
    沈念sama閱讀 44,110評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡锥累,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了石咬。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,577評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡卖哎,死狀恐怖鬼悠,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情亏娜,我是刑警寧澤焕窝,帶...
    沈念sama閱讀 34,258評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站维贺,受9級特大地震影響它掂,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜溯泣,卻給世界環(huán)境...
    茶點故事閱讀 39,848評論 3 312
  • 文/蒙蒙 一虐秋、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧垃沦,春花似錦客给、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,726評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽蜻拨。三九已至,卻和暖如春桩引,著一層夾襖步出監(jiān)牢的瞬間缎讼,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,952評論 1 264
  • 我被黑心中介騙來泰國打工坑匠, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留血崭,地道東北人。 一個月前我還...
    沈念sama閱讀 46,271評論 2 360
  • 正文 我出身青樓笛辟,卻偏偏與公主長得像功氨,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子手幢,可洞房花燭夜當晚...
    茶點故事閱讀 43,452評論 2 348

推薦閱讀更多精彩內(nèi)容

  • 算法包括三部分:算法思想 + 排序算法 + 查找算法 算法思想: 算法思想 就是 解題思路捷凄。常見的解題思路有如下:...
    小酷哥閱讀 947評論 2 14
  • 龔老師的電腦最近脾氣很大,因為最近我總讓它做枚舉算法围来,可把它累壞了跺涤。枚舉算法大家還記得吧,先來復習一下找找為什么電...
    GBangBang閱讀 537評論 0 1
  • 《惜春》 雨晨擎?zhèn)闱嗌饺ィ?樹下聽風響沙沙监透。 遙憶當年石溪坐桶错, 靜觀流水逐山花。
    相山雨晨閱讀 474評論 2 11
  • 最近常常想到《無問西東》里面的這幾段臺詞: 如果提前了解了你們要面對的人生,不知你們是否還會有勇氣前來粪狼,看見和聽到...
    桃子小播閱讀 285評論 0 1
  • 第一章 冷酷而溫柔 一層云一層紗退腥,夢里的你如花。 那年我16歲再榄,剛進天村一中狡刘,第一次遇見他就是在那個槐花飄香的季節(jié)...
    離開樹的櫻桃還會不會長大閱讀 685評論 23 13