算法練習(14):直方圖(1.1.32)

本系列博客習題來自《算法(第四版)》可柿，算是本人的讀書筆記彻桃，如果有人在讀這本書的篮绰，歡迎大家多多交流钉鸯。為了方便討論，本人新建了一個微信群(算法交流)鼓鲁，想要加入的蕴轨，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外骇吭，本人的個人博客 http://www.kyson.cn 也在不停的更新中橙弱，歡迎一起討論

算法(第4版)

知識點

直方圖概念

題目

1.1.32 直方圖。假設(shè)標準輸入流中含有一系列 double 值。編寫一段程序棘脐，從命令行接受一個整數(shù) N 和兩個 doubl 值 l 和 r斜筐。將 (l，r) 分為 N 段并使用 StdDraw 畫出輸入流中的值落入每段的數(shù)量的直方圖蛀缝。

1.1.32 Histogram. Suppose that the standard input stream is a sequence of double values. Write a program that takes an integer N and two double values l and r from the command line and uses StdDraw to plot a histogram of the count of the numbers in the standard input stream that fall in each of the N intervals defined by dividing (l , r) into N equal-sized intervals.

分析

在習題算法練習(3) :遞歸(1.1.15-1.1.21)中顷链，我們已經(jīng)接觸了直方圖，下面我們再詳細的講一下直方圖屈梁。

直方圖(Histogram)又稱質(zhì)量分布圖嗤练。是一種統(tǒng)計報告圖，由一系列高度不等的縱向條紋或線段表示數(shù)據(jù)分布的情況在讶。一般用橫軸表示數(shù)據(jù)類型煞抬，縱軸表示分布情況。
應(yīng)用步驟
(1)收集數(shù)據(jù)构哺。作直方圖的數(shù)據(jù)一般應(yīng)大于50個革答。
　　(2)確定數(shù)據(jù)的極差(R)。用數(shù)據(jù)的最大值減去最小值求得遮婶。
　　(3)確定組距(h)蝗碎。先確定直方圖的組數(shù)湖笨，然后以此組數(shù)去除極差旗扑，可得直方圖每組的寬度，即組距慈省。組數(shù)的確定要適當臀防。組數(shù)太少，會引起較大計算誤差边败；組數(shù)太多袱衷，會影響數(shù)據(jù)分組規(guī)律的明顯性，且計算工作量加大笑窜。
　　(4)確定各組的界限值致燥。為避免出現(xiàn)數(shù)據(jù)值與組界限值重合而造成頻數(shù)據(jù)計算困難，組的界限值單位應(yīng)取最小測量單位的1/2排截。分組時應(yīng)把數(shù)據(jù)表中最大值和最小值包括在內(nèi)嫌蚤。
　　第一組下限值為：最小值-0.5;
　　第一組上限值為：第一組下限值加組距;
　　第二組下限值就是第一組的上限值；
　　第二組上限值就是第二組的下限值加組距断傲；
　　第三組以后脱吱，依此類推定出各組的組界。
　　(5)編制頻數(shù)分布表认罩。把多個組上下界限值分別填入頻數(shù)分布表內(nèi)箱蝠，并把數(shù)據(jù)表中的各個數(shù)據(jù)列入相應(yīng)的組，統(tǒng)計各組頻數(shù)據(jù)(f )。
　　(6)按數(shù)據(jù)值比例畫出橫坐標宦搬。
　　(7)按頻數(shù)值比例畫縱坐標牙瓢。以觀測值數(shù)目或百分數(shù)表示。
　　(8)畫直方圖间校。按縱坐標畫出每個長方形的高度一罩，它代表取落在此長方形中的數(shù)據(jù)數(shù)。(注意：每個長方形的寬度都是相等的撇簿。)在直方圖上應(yīng)標注出公差范圍(T)聂渊、樣本容量(n)、樣本平均值(x)四瘫、樣本標準偏差值(s)和x的位置等汉嗽。

StdDraw庫
在書中，有一個展示繪制矩形的代碼找蜜，截圖如下：

/*
* demo :用于展示StdDraw.filledRectangle 的用法
*/
int N = 50;
double[] a = new double[N];
for (int i = 0; i < N; i++)
    a[i] = StdRandom.random();

for (int i = 0; i < N; i++) {
    double x = 1.0 * i / N;
    double y = a[i] / 2.0;
    double rw = 0.5 / N;
    double rh = a[i] / 2.0;
    StdDraw.filledRectangle(x, y, rw, rh);
}

我們來分析一下這個代碼饼暑，主要是方法filledRectangle ，
他的API文檔在書中是這么寫的
static void filledRectangle(double x, double y, double rw, double rh)
四個參數(shù)分別為
x: 這個矩形的起始x坐標
y:這個矩形的起始x坐標
rw：寬度
rh：高度
關(guān)于StdDraw庫后面還有相應(yīng)的文章會提到洗做，大家后面會對它越來越有深入的了解

視頻講解

點此觀看分析視頻:直方圖介紹
 點此觀看分析視頻:習題答案

答案

public class Histogram {

    public static void main(String[] args) {

        double[] a = { 1.12, 1.22, 5.666, 9.0908, 8.902, 3.892, 10.782, 10.9,
                10.19, 10.29, 20.1 };
        int N = 10;
        double l = 1.09;
        double r = 20.29;

        // 組距
        double classInterval = (r - l) / N;
        // 對應(yīng)到直方圖中的組距
        double intervalReact = 1 * 1.0 / N;

        for (int i = 0; i < N; i++) {
            // 每組數(shù)據(jù)的左值和右值
            double tempLeft = l + classInterval * i;
            double tempRight = l + classInterval * (i + 1);
            // 每組數(shù)據(jù)的左值對應(yīng)到直方圖中的左值
            double tempLeftReact = intervalReact * i;

            /**
             * 以下代碼塊是用于輸入流在計算該組數(shù)下的頻數(shù)
             */
            int tempNum = 0;
            for (int j = 0; j < a.length; j++) {
                if (a[j] > tempLeft && a[j] < tempRight) {
                    tempNum++;
                }
            }
            // 將頻數(shù)轉(zhuǎn)換為頻率
            double height = tempNum * 1.0 / (N * 2);
            // 畫圖
            StdDraw.filledRectangle(tempLeftReact, height, intervalReact,
                    height);
        }

    }

}

代碼索引

Histogram.java

算法練習(14):直方圖(1.1.32)

知識點

題目

分析

視頻講解

答案

代碼索引

廣告