国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Algorithms(第四版)1.1課后練習答案(個人整理)

android_c / 937人閱讀

摘要:最近著手學習的這本書,開始做習題時發現配套網站上對應的習題答案并不完全,后發現以及有些人的博客上有部分答案,不過一般只做了第一章節的題目,大概是題目太多了的原因,在此自己整理自己所做的一份答案,希望有同行的人一起交流,分享。

最近著手學習Robert Sedgewick的Algorithms這本書,開始做習題時發現配套網站上對應的習題答案并不完全,google后發現github以及有些人的博客上有部分答案,不過一般只做了第一章節的題目,大概是題目太多了的原因,在此自己整理自己所做的一份答案,希望有同行的人一起交流,分享。

練習

1.1.1
a.7
b.200.0000002
c.true

1.1.2
a.1.618
b.10.0
c.true
d.33

1.1.3
需要添加對應官方網站上所提供的標準輸入庫函數StdIn.java

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_3 {
    public static void main(String[] args) {
        int a=StdIn.readInt();
        int b=StdIn.readInt();
        int c=StdIn.readInt();
        if(a==b&&a==c)
            System.out.println("equal");
        else
            System.out.println("not equal");
    }
}

1.1.4
a.多余了then(VB有這種語法)
b.a>b缺少()
c.正確
d.c=0缺少;

1.1.5

package Chapter1;

import edu.princeton.cs.algs4.*;

public class parc1_1_5 {
    public static void main(String[] args) {
        double x=StdIn.readDouble();
        double y=StdIn.readDouble();
        
        if(x>=0&&x<=1&&y>=0&&y<=1)
            System.out.println(true);
        else
            System.out.println(false);
    }
}

1.1.6
一段Fibonacci

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610

1.1.7
a.3.00009 應該是計算算數平方根
b.499500 計算 1+2+3+...+999也就是(1+999)*999/2
c.10000 1000*10,就外循環來看一共十個輪回(2^0,2^1,...,2^9=512<1000,2^10=1024>1000,而內循環每次執行1000次)

1.1.8 (考察 ASCII表格 )
a.b
b.197 (默認是會轉換為相加后的數字輸出)
c.e

1.1.9

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_9 {

    public static void main(String[] args) {
        int N;
        //count the binary form of N
        while((N=StdIn.readInt())>0){
            String s="";
            while(N/2!=0){
                s+=(N%2);
                N/=2;
            }
            s+="1";
            //reverse the string s            
            char[] ch=new char[s.length()];            
            for(int i=0;i

【還是思維形成定勢了,基本運算一致,未曾想從右邊加,就像鏈表的頭插尾插一樣】
附課本源代碼

String s="";
for(int n=N;n>0;n/=2)
   s=(n%2)+s;

1.1.10

在新建一個數組時未給該數組用new分配內存,會產生 variable a might not have been initialized的編譯錯誤

1.1.11

package Chapter1;

public class prac1_1_11 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        boolean[][] array={{true,false,false},{false,false,true},{true,false,true}};
        //print the column number
        System.out.print(" ");
        for(int i=0;i

關于這個題不知道我的理解是否正確,因為和網上查到的另一個朋友的答案不一樣,他是直接輸出每一個位置+元素,而我的理解是仍保持矩陣的形式將對應的boolean值替換為"*"和‘ ’,并輸出行號,列號,由于沒有標準答案,見仁見智吧

別人的結果以及原鏈接

我個人的對應的結果

1.1.12

1.1.13

package Chapter1;

public class prac1_1_13 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] a={{1,2,3},{7,5,1}};
        //print 2D array
        System.out.println("before transfer");
        printArray(a);
        System.out.println("after transfer");
        //transfer the 2D array
        printArray(transferArray(a));
    }
    
    public static void printArray(int[][] a){
        for(int i=0;i

1.1.14

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_14 {

    public static void main(String[] args) {
        int N=StdIn.readInt();
        System.out.println(lg(N));
    }
    
    public static int lg(int N){
        int lg=0;
        for(int i=0;iN){
                lg=i;
                break;
            }
        }
        return lg;
    }
    
    public static int myPow(int m,int n){
        int temp=m;
        while(--n>0){
            m*=temp;
        }
        return m;
    }

}

1.1.15

package Chapter1;

public class prac1_1_15 {

    public static void main(String[] args) {
        int[] testArray={1,1,2,3,1,7,5,3,2,2,2};
        System.out.println("histogram result");
        printArray(histogram(testArray, 8));
    }
    
    public static int[] histogram(int[] a,int M){
        int[] hArray=new int[M];
        for(int i=0;i

1.1.16
311361142246

1.1.17

該代碼中的基礎情況永遠不會被調用,因為調用exR2(3)會產生調用exR2(0),exR2(-3)和exR2(-6),循環往復直至產生StackOverflowError.

1.1.18
乘法的遞歸實現
mystery(2,25)=50
mystery(3,11)=33
mystery(a,b)=a*b
修改后結果:
乘方的遞歸實現
mystery(a,b)=a^b

1.1.19

package Chapter1;

public class prac1_1_19 {

    public prac1_1_19() {
        int[] F = new int[100];
        F[0] = 0;
        F[1] = 1;
        for(int i=2;i<100;++i)
            F[i]=F[i-1]+F[i-2];
        System.out.println(F[30]);
    }

    public static void main(String[] args) {
        prac1_1_19 test=new prac1_1_19();

    }

}

1.1.20

package Chapter1;

import java.lang.Math;
import edu.princeton.cs.algs4.*;

public class prac1_1_20 {

    public static void main(String[] args) {
        int N=StdIn.readInt();
        System.out.println(ln(N));
    }

    public static double ln(int N){
        if(N==1)
            return 0;
        return ln(N-1)+Math.log(N);
    }
}

由于此題考察遞歸,所以對于ln的計算是調用Math里的現成庫

1.1.21

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_21 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        while(StdIn.hasNextLine()){
            String name=StdIn.readString();
            int m=StdIn.readInt();
            int n=StdIn.readInt();
            StdOut.printf("%8s | %8d | %8d | %8.3f", name,m,n,(m*1.0)/n);
        }    
    }
}

1.1.22

package Chapter1;

public class prac1_1_22 {
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array={1,3,5,7,9};
        int location=rank(3,array,0);
        if(location<0)
            System.out.println("key not found");
        else
            System.out.println("key location="+(location+1));

    }

    public static int rank(int key, int[] a,int depth) {
        return rank(key, a, 0, a.length - 1,depth);
    }

    private static int rank(int key, int[] a, int lo, int hi,int dep) {
        // TODO Auto-generated method stub
        for(int i=0;i hi)
            return -1;
        int mid = (lo + hi) / 2;
        if (key < a[mid])
            return rank(key, a, lo, mid - 1,dep);
        else if (key > a[mid])
            return rank(key, a, mid + 1, hi,dep);
        else
            return mid;
    }
}

1.1.23

折騰了大半天,最后找到別人的一份代碼應該是符合條件的

/**
 * 二分查找 : 非遞歸描述
 * @param key   關鍵字
 * @param arr   數組
 * @return  若找到則返回true,否則返回false
 */
public static boolean BinaryLookup(int key, int[] arr) {
    int low = 0;
    int high = arr.length - 1;
    while(low <= high) {
        int mid = low + ((high - low) >> 1);
        if(key < arr[mid])
            high = mid - 1;
        else if(key > arr[mid])
            low = mid + 1;
        else
            return true;
    }
    return false;
}

public static void main(String[] args) {
    // “ + ” --> 打印出標準輸入中不在白名單上的值,
    // “ - ” --> 打印出標準輸入中在白名單上的值
    char symbol = "-";
    int[] whitelist = new In(args[0]).readAllInts();
    Arrays.sort(whitelist);
    while(!StdIn.isEmpty()) {
        int key = StdIn.readInt();
        boolean found = BinaryLookup(key, whitelist);
        if("+" == symbol && !found)
            StdOut.println(key);
        if("-" == symbol && found)
            StdOut.println(key);
    }
}

不過需要注意的是,在windows的環境下的控制臺直接調用書上的命令是行不通的,首先是調用了書上一直在提的 algs4.jar,然后是需要從命令行讀取文件進行比對,而windows控制臺是沒法運行書上所述的

java xxx largeW.txt < largeT.txt

即使將需要用到的作者寫好的庫放在java文件的同一目錄下也會產生如下異常

可能是命令行不支持“<”命令吧,因為最近聯系到這段代碼的作者,發現他是在Linux系統下編譯執行的,據說是沒問題。

經過一番查找,最終我發現有一種方法是用本書作者開發的一套控制臺程序,然后按照該連接的操作,使用如下指令進行編譯和運行才可以成功

javac-algs4 xxx.java  //編譯指令

java-algs4 xxx largeW.txt < largeT.txt    //執行指令

當然注意其中的largeW.txtlargeT.txt也來自相應網站的data文件里,需要放到和java文件相同目錄

【更新】后來我在stackoverflow上提問,有人解答了,在windows上的命令應該是這樣的

Get-Content tinyT.txt | java prac1_1_23 tinyW.txt

不過比較奇怪的是,用原始的largeW.txtlargeT.txt的話PowerShell就直接崩潰了,應該是數據量過大的緣故吧,但是用所提供的CLI倒是可以跑

【更新】此外,cmd是可以直接執行的,另外一種方法是把命令寫為".bat"文件然后執行該文件,效果類似,倒是破除了PowerShell一定優于cmd的封建迷信了,stackoverflow上的朋友還是相當熱心嚴謹那~

【更新】若堅持使用powershell,stackoverflow上有人提出可以用如下指令,親測有效

cmd /c --% java prac1_1_23 largeW.txt < largeT.txt

若有更好的方法還希望能不吝賜教

1.1.24

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_24 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        while(StdIn.hasNextLine()){
            int x=StdIn.readInt();
            int y=StdIn.readInt();
            StdOut.println("the greatest common divisor of "+x+" and "+y+" is: "+gcd(x,y));
        }
    }
    
    public static int gcd(int a,int b){
        StdOut.println(a+" "+b);
        int m=max(a,b);
        int n=min(a,b);
        if(m%n==0)
            return n;
        else
            return gcd((m%n),n);
    }
    
    public static int max(int a,int b){
        if(a>=b)
            return a;
        else
            return b;
    }
    
    public static int min(int a,int b){
        if(a>=b)
            return b;
        else
            return a;
    }

}

輸出結果如下

考慮到讓用戶輸入不一定按先大后小的順序輸入所以加入了一點預處理

1.1.25
網上找的證明1,證明2

提高題

1.1.26
本質上是在說java里的變量的值的交換的算法,需要第三個數來進行臨時存儲從而完成交換,其實也有另一種方法,通過兩次異或運算‘^’完成交換操作

a=a^b;
b=b^a;   //此時b變為a
a=a^b;    //此時a變為b

1.1.27
第一問是向遞歸函數里添加了一個計數器參數,使用了第二節的現有的計數器類,每次調用遞歸時即遞增一次,代碼如下:

package Chapter1;

import Chapter1.Counter;
import edu.princeton.cs.algs4.StdOut;

public class prac1_1_27 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=Integer.parseInt(args[0]),
            k=Integer.parseInt(args[1]);
        double p=Double.parseDouble(args[2]);
        
        Counter c=new Counter("calls");
        double b=binomial(n,k,p,c);
        
        StdOut.println(b);
        StdOut.println(c);
        
    }
    
    public static double binomial(int N, int k, double p,Counter c){
        double[][] a=new double[N+1][k+1];
        for(int i=0;i<=N;++i){
            for(int j=0;j<=k;++j){
                a[i][j]=-1;
            }
        }
        return binomial(a,N,k,p,c);
    }

    private static double binomial(double[][] a, int N, int k, double p, Counter c) {
        if(N==0&&k==0)
            return 1.0;
        if(N<0||k<0)
            return 0.0;
        if(a[N][k]==-1){
            c.increment();
            a[N][k]=(1.0-p)*binomial(a,N-1,k,p,c)+p*binomial(a,N-1,k-1,p,c);
        }
        return a[N][k];
    }

}

第二道題是用空間換時間的應用,用二維數組來存取所計算的概率值,這樣以后計算某一概率的值時可直接從數組中讀,而不必重復計算前面已經計算過的值;

package Chapter1;

import Chapter1.Counter;
import edu.princeton.cs.algs4.StdOut;

public class prac1_1_27 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=Integer.parseInt(args[0]),
            k=Integer.parseInt(args[1]);
        double p=Double.parseDouble(args[2]);
        
        Counter c=new Counter("calls");
        double b=binomial(n,k,p,c);
        
        StdOut.println(b);
        StdOut.println(c);
        
    }
    
    public static double binomial(int N, int k, double p,Counter c){
        double[][] a=new double[N+1][k+1];
        for(int i=0;i<=N;++i){
            for(int j=0;j<=k;++j){
                a[i][j]=-1;
            }
        }
        return binomial(a,N,k,p,c);
    }

    private static double binomial(double[][] a, int N, int k, double p, Counter c) {
        if(N==0&&k==0)
            return 1.0;
        if(N<0||k<0)
            return 0.0;
        if(a[N][k]==-1){
            c.increment();
            a[N][k]=(1.0-p)*binomial(a,N-1,k,p,c)+p*binomial(a,N-1,k-1,p,c);
        }
        return a[N][k];
    }

}

參考1參考2

1.1.28
這道題我的想法是遍歷已排序后的數組逐一判斷元素是否和前一元素相同,若不相同則用一個list來收集,最后利用list的內置方法直接將list轉換為數組即可

public static Integer[] distinctArray(int[] whitelist) {
        List list=new ArrayList<>();
        list.add(whitelist[0]);
        for(int i=1;i

對應的主函數如下

public static void main(String[] args) {
        // TODO Auto-generated method stub
//        int[] whitelist=In.readInts(args[0]);
        int[] whitelist={1,3,3,3,5,6,6,7,};
        Arrays.sort(whitelist);
        for(int i=0;i

1.1.29
這道題我一開始想簡單了就直接遍歷了,殊不知既然是寫在二分查找這一類中的方法自然應該利用二分查找的方式去提高效率,正確的做法是對之前尋找到middle的部分進行修改

package Chapter1;

public class prac1_1_29 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a={1,2,3,3,3,4,5,5,6,8};
        int i=rank(3,a);
        int j=count(3,a);
        System.out.println(i+" "+j);
//        for(int k=i;k<=i+j-1;++k){
//            System.out.print(a[k]+" ");
//        }
    }
    
    public static int rank(int key,int[] array){
        int low=0; 
        int high=array.length-1;
        while(low<=high){
            int    middle=(low+high)>>1;
            if(keyarray[middle])
                low=middle+1;
            else if(key==array[middle]){
                while(middle>0&&array[middle]==key)
                    middle--;
                return middle+1;
            }                
        }
        return -1;
    }
    
    public static int count(int key,int[] array){
        int count=0;
        int lower=rank(key,array);
        for(int i=lower;i

1.1.30
判斷是否互質,個人是事先判斷了下兩個數的大小以便進行遍歷

package Chapter1;

public class prac1_1_30 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        boolean[][] a=new boolean[3][19];
        for(int i=0;ij){
            i=i^j;
            j=j^i;
            i=i^j;
        }
        for(int k=2;k<=i;k++)
            if(j%k==0&&i%k==0)
                return false;
        return true;
    }
}

測試結果

實驗題

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65140.html

相關文章

  • iKcamp出品|全網最新|微信小程序|基于最新版1.0開發者工具之初中級培訓教程分享

    摘要:微信小程序課程,面向所有具備前端基礎知識的同學官網訪問官網更快閱讀全部免費分享課程出品全網最新微信小程序基于最新版開發者工具之初中級培訓教程分享。 ?? 微信小程序課程,面向所有具備前端基礎知識的同學 ?? iKcamp官網:http://www.ikcamp.com 訪問官網更快閱讀全部免費分享課程:《iKcamp出品|全網最新|微信小程序|基于最新版1.0開發者工具之初中級培訓教...

    hersion 評論0 收藏0
  • iKcamp出品|全網最新|微信小程序|基于最新版1.0開發者工具之初中級培訓教程分享

    摘要:微信小程序課程,面向所有具備前端基礎知識的同學官網訪問官網更快閱讀全部免費分享課程出品全網最新微信小程序基于最新版開發者工具之初中級培訓教程分享。 ?? 微信小程序課程,面向所有具備前端基礎知識的同學 ?? iKcamp官網:http://www.ikcamp.com 訪問官網更快閱讀全部免費分享課程:《iKcamp出品|全網最新|微信小程序|基于最新版1.0開發者工具之初中級培訓教...

    MRZYD 評論0 收藏0
  • iKcamp出品|全網最新|微信小程序|基于最新版1.0開發者工具之初中級培訓教程分享

    摘要:微信小程序課程,面向所有具備前端基礎知識的同學官網訪問官網更快閱讀全部免費分享課程出品全網最新微信小程序基于最新版開發者工具之初中級培訓教程分享。 ?? 微信小程序課程,面向所有具備前端基礎知識的同學 ?? iKcamp官網:http://www.ikcamp.com 訪問官網更快閱讀全部免費分享課程:《iKcamp出品|全網最新|微信小程序|基于最新版1.0開發者工具之初中級培訓教...

    李昌杰 評論0 收藏0
  • iKcamp出品微信小程序教學共5章16小節匯總(含視頻)

    摘要:微信小程序課程,面向所有具備前端基礎知識的同學閱讀要求讀者需要具備但不限于以下技能更佳一共四部分十五小節,適合七天的訓練營。 ?? 微信小程序課程,面向所有具備前端基礎知識的同學 ?? 閱讀要求 讀者需要具備但不限于以下技能 HTML JavaScript es6更佳 CSS 一共四部分十五小節,適合七天的訓練營。 從現在開始,我假裝你已經掌握了 html、 css以及 ES6...

    elliott_hu 評論0 收藏0
  • iKcamp出品微信小程序教學共5章16小節匯總(含視頻)

    摘要:微信小程序課程,面向所有具備前端基礎知識的同學閱讀要求讀者需要具備但不限于以下技能更佳一共四部分十五小節,適合七天的訓練營。 ?? 微信小程序課程,面向所有具備前端基礎知識的同學 ?? 閱讀要求 讀者需要具備但不限于以下技能 HTML JavaScript es6更佳 CSS 一共四部分十五小節,適合七天的訓練營。 從現在開始,我假裝你已經掌握了 html、 css以及 ES6...

    paney129 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<