經(jīng)典遞歸算法輔導(dǎo)講解課件-藍(lán)橋杯軟件大賽輔導(dǎo)-技能大賽

遞歸與分治(fēnzhì)策略共六十頁(yè)將要求解的較大規(guī)模的問(wèn)題(wèntí)分割成k個(gè)更小規(guī)模的子問(wèn)題(wèntí)。算法總體(zǒngtǐ)思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。共六十頁(yè)算法(suànfǎ)總體思想對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠(zúgòu)小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。共六十頁(yè)算法(suànfǎ)總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)(yīɡè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)共六十頁(yè)自頂向下、逐步(zhúbù)分解的策略將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步(zhúbù)求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。(1)子問(wèn)題應(yīng)與原問(wèn)題做同樣的事情，且更為簡(jiǎn)單；(2)解決遞歸問(wèn)題的策略是把一個(gè)規(guī)模比較大的問(wèn)題分解為一個(gè)或若干規(guī)模比較小的問(wèn)題，分別對(duì)這些比較小的問(wèn)題求解，再綜合它們的結(jié)果，從而得到原問(wèn)題的解?！侄沃呗裕ǚ种畏ǎ?3)這些比較小的問(wèn)題的求解方法與原來(lái)問(wèn)題的求解方法一樣。

共六十頁(yè)遞歸的概念(gàiniàn)直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)(jìshù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。共六十頁(yè)遞歸的三個(gè)條件(tiáojiàn)1、邊界條件2、遞歸前進(jìn)段3、遞歸返回(fǎnhuí)段當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸(求和)求1+2+3+…+n:邊界條件遞歸方程(fāngchéng)共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸(求和)publicstaticintsum(intn){if(n>1){returnn+sum(n-1);//調(diào)用遞歸方法}else{return1;//當(dāng)n=1時(shí)，循環(huán)(xúnhuán)結(jié)束}共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（階乘）

例1階乘函數(shù)(hánshù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（階乘）publicstaticintf(intn){

if(1==n)

return1;

else

returnn*(n-1);

}

共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（階乘）共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（階乘）共六十頁(yè)主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：6(1)3top返回(3)1(2)2(1)3top(4)0結(jié)束(1)遞歸調(diào)用執(zhí)行(zhíxíng)情況共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（十進(jìn)制轉(zhuǎn)二進(jìn)制）static

voidd2b(intn){if(n==0||n==1);//System.out.print(n);//遞歸出口(chūkǒu)elsed2b(n/2);System.out.print(n%2);}共六十頁(yè)遞歸的目的(mùdì)使用遞歸的目的在于解決一種常見(jiàn)問(wèn)題(wèntí)，即子任務(wù)只不過(guò)是開(kāi)始試圖解決的相同問(wèn)題(wèntí)的一個(gè)較簡(jiǎn)單版本。共六十頁(yè)簡(jiǎn)單的遞歸（縱向(zònɡxiànɡ)顯示整數(shù)）例子：在屏幕上以十進(jìn)制打印(dǎyìn)一個(gè)非負(fù)整數(shù)，要求所有位縱向顯示在屏幕上。舉例來(lái)說(shuō)1234顯示如下1234可以劃分為2個(gè)問(wèn)題：縱向打印出除最后一位之外的所有位；打印最后一位。把1234記為number。共六十頁(yè)簡(jiǎn)單的遞歸（縱向顯示(xiǎnshì)整數(shù)）應(yīng)該這樣打印：123第二步輸出4第一步需要123，可以表示為number/10。第二步表示為number%10。按照遞歸的思想(sīxiǎng)，其中一步——縱向打印number/10的所有位，是同一個(gè)縱向打印數(shù)字問(wèn)題的一個(gè)比較簡(jiǎn)單的實(shí)例。因?yàn)閚umber/10比number少了一位，所以比較簡(jiǎn)單，就可調(diào)用方法自身來(lái)實(shí)現(xiàn)。共六十頁(yè)簡(jiǎn)單的遞歸（縱向(zònɡxiànɡ)顯示整數(shù)）方法(fāngfǎ)writeVertical的實(shí)現(xiàn)public

static

voidwriteVertical(intnumber){if(number<10){System.out.println(number);}else{writeVertical(number/10);System.out.println(number%10);}}共六十頁(yè)簡(jiǎn)單的遞歸（縱向(zònɡxiànɡ)顯示整數(shù)）停止條件如果問(wèn)題足夠簡(jiǎn)單，就可以不用遞歸調(diào)用解決。對(duì)于writeVertical，這發(fā)生在number只有一位時(shí)。這種沒(méi)有任何遞歸的情況叫做停止條件或基本(jīběn)條件。在writeVertical方法中，停止條件由三行代碼實(shí)現(xiàn)：if(number<10){System.out.println(number);}共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（縱向顯示整數(shù)）遞歸調(diào)用else{writeVertical(number/10);System.out.println(number%10);}writeVertical方法調(diào)用它自己去解決比較簡(jiǎn)單的問(wèn)題，即打印(dǎyìn)最后一位數(shù)字之外的所有位。共六十頁(yè)遞歸的概念(gàiniàn)對(duì)writeVertical進(jìn)行擴(kuò)展(kuòzhǎn)，以處理所有整數(shù)，包括負(fù)數(shù)。當(dāng)輸入負(fù)號(hào)時(shí)，新方法在輸出的第一行打印負(fù)號(hào)，然后再是其他的位。怎么處理負(fù)數(shù)？打印負(fù)號(hào)，然后用-1×number把number變?yōu)檎龜?shù)。請(qǐng)嘗試寫(xiě)出方法superWriteVertical(intnumber)共六十頁(yè)遞歸的概念(gàiniàn)public

static

voidsuperWriteVertical(intnumber){if(number<0){System.out.println("-");superWriteVertical(-number);}else

if(number<10){System.out.println(number);}else{writeVertical(number/10);System.out.println(number%10);}}共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（斐波那契）例2Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以(kěyǐ)遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：intfibonacci(intn){

if(n<=2)return1;

return

fibonacci(n-1)+fibonacci(n-2);}共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（斐波那契）共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（斐波那契）staticintf(intn) { if(n==1||n==2)return1;//遞歸出口(chūkǒu) returnf(n-1)+f(n-2); }

共六十頁(yè)求兩個(gè)(liǎnɡɡè)正整數(shù)m,n(m<n)的最大公約數(shù)簡(jiǎn)單(jiǎndān)的遞歸（最大公約數(shù)）遞規(guī)定義：gcd(m,n)=gcd(n%m,m)n%m!=0gcd(m,n)=mn%m==0共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（最大公約數(shù)）static

intgcd(inta,intb){if(b==0)returna;elsereturn

gcd(b,a%b);}共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（最大公約數(shù)）程序從main開(kāi)始，再到你定義的方法gcd，進(jìn)行(jìnxíng)調(diào)用，80%50不等于0，執(zhí)行else語(yǔ)句，到gcd在進(jìn)行(jìnxíng)調(diào)用gcd方法，不過(guò)2個(gè)參數(shù)為50和80%50的值30，50%30不等于0，繼續(xù)調(diào)用gcd方法，直到if(a%b==0)的值為T(mén)RUE為止，結(jié)果返回給intt繼續(xù)執(zhí)行剩下的語(yǔ)句。借用回答者：緣心風(fēng)絕

80%50=30

50%30=20

30%20=10

20%10=0出遞歸

10是最大公約數(shù)。這樣比較清楚共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（最大公約數(shù)2）n利用計(jì)算最大公約數(shù)的三條性質(zhì)(xìngzhì)，用遞歸方法計(jì)算兩個(gè)整數(shù)的最大公約數(shù)。

n性質(zhì)(xìngzhì)1：如果x>y，則x和y的最大公約數(shù)與x-y和y的最大公約數(shù)相同，即gcd(x,y)=gcd(x-y,y)

x>y

n性質(zhì)(xìngzhì)2：如果y>x，則x和y的最大公約數(shù)與x和y-x的最大公約數(shù)相同，即gcd(x,y)=gcd(x,y-x)

x<y

n性質(zhì)(xìngzhì)3：如果x=y，則x和y的最大公約數(shù)與x值和y值相同，即gcd(x,y)=x=y共六十頁(yè)設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起(yīqǐ)。各圓盤(pán)從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。簡(jiǎn)單(jiǎndān)的遞歸（Hanoi塔問(wèn)題）共六十頁(yè)在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此(yīncǐ)我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤(pán)從塔座a直接移至塔座b上即可。當(dāng)n＞1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤(pán)從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見(jiàn)，n個(gè)圓盤(pán)的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤(pán)的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法(fāngfǎ)來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法如下。

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}簡(jiǎn)單的遞歸（Hanoi塔問(wèn)題）共六十頁(yè)簡(jiǎn)單(jiǎndān)的遞歸（Hanoi塔問(wèn)題）

有些問(wèn)題的求解方法(fāngfǎ)是遞歸的，典型有漢諾塔問(wèn)題求解：共六十頁(yè)漢諾塔問(wèn)題(wèntí)求解盤(pán)片移動(dòng)時(shí)必須遵守(zūnshǒu)以下規(guī)則：每次只能移動(dòng)一個(gè)盤(pán)片；盤(pán)片可以插在A、B、C中任一塔座；不能將一個(gè)較大盤(pán)片的放在較小的盤(pán)片上。共六十頁(yè)漢諾塔問(wèn)題(wèntí)求解共六十頁(yè)3.遞歸算法的設(shè)計(jì)(shèjì)方法

遞歸算法既是一種(yīzhǒnɡ)有效的算法設(shè)計(jì)方法，也是一種(yīzhǒnɡ)有效的分析問(wèn)題的方法。遞歸算法求解問(wèn)題的基本思想是：對(duì)于一個(gè)較為復(fù)雜的問(wèn)題，把原問(wèn)題分解成若干個(gè)相對(duì)簡(jiǎn)單且類同的子問(wèn)題,這樣，原問(wèn)題就可遞推得到解。適宜于用遞歸算法求解的問(wèn)題的充分必要條件是：（1）問(wèn)題具有某種可借用的類同自身的子問(wèn)題描述的性質(zhì)；（2）某一有限步的子問(wèn)題（也稱作本原問(wèn)題）有直接的解存在。當(dāng)一個(gè)問(wèn)題存在上述兩個(gè)基本要素時(shí)，該問(wèn)題的遞歸算法的設(shè)計(jì)方法是：（1）把對(duì)原問(wèn)題的求解設(shè)計(jì)成包含有對(duì)子問(wèn)題求解的形式。（2）設(shè)計(jì)遞歸出口。共六十頁(yè)例如：設(shè)計(jì)(shèjì)模擬漢諾塔問(wèn)題求解過(guò)程的算法。問(wèn)題描述：設(shè)有3根標(biāo)號(hào)為A，B，C的柱子，在A柱上放著n個(gè)盤(pán)子，每一個(gè)都比下面的略小一點(diǎn)，要求把A柱上的盤(pán)子全部移到C柱上，移動(dòng)的規(guī)則是：（1）一次只能移動(dòng)一個(gè)盤(pán)子；（2）移動(dòng)過(guò)程中大盤(pán)子不能放在小盤(pán)子上面；（3）在移動(dòng)過(guò)程中盤(pán)子可以放在A，B，C的任意一個(gè)柱子上。共六十頁(yè)問(wèn)題分析：可以用遞歸方法求解n個(gè)盤(pán)子的漢諾塔問(wèn)題。解決方法：當(dāng)n=1時(shí)，直接把圓盤(pán)從A移到C；當(dāng)n>1時(shí)，先把上面n-1個(gè)圓盤(pán)從A移到B,然后將n號(hào)盤(pán)從A移到C,再將n-1個(gè)盤(pán)從B移到C。即把求解n個(gè)圓盤(pán)的Hanoi問(wèn)題轉(zhuǎn)化為求解n-1個(gè)圓盤(pán)的Hanoi問(wèn)題，依次(yīcì)類推，直至轉(zhuǎn)化成只有一個(gè)圓盤(pán)的Hanoi問(wèn)題。4個(gè)盤(pán)子漢諾塔問(wèn)題的遞歸求解示意圖如圖所示。

共六十頁(yè)漢諾塔問(wèn)題(wèntí)的遞歸求解示意圖

共六十頁(yè)求N階漢諾塔的遞歸算法(suànfǎ)：voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(x,n,z);/*將1號(hào)盤(pán)從x座移到z座*/(4)else{(5)hanoi(n-1,x,z,y);/*將x座上n-1個(gè)圓盤(pán)(yuánpán)移到y(tǒng)座，z座作為輔助*/(6)move(x,n,z);/*將n號(hào)盤(pán)從x座移到z座*/(7)hanoi(n-1,y,x,z);/*將y座上n-1個(gè)圓盤(pán)移到z座，x座作為輔助*/(8)}(9)}共六十頁(yè)4．遞歸過(guò)程(guòchéng)的實(shí)現(xiàn)遞歸函數(shù)被調(diào)用(diàoyòng)時(shí)，系統(tǒng)需要一個(gè)運(yùn)行工作棧.系統(tǒng)的運(yùn)行工作棧要保存兩類信息：（1）調(diào)用函數(shù)的返回地址；（2）調(diào)用函數(shù)的局部變量值。每一層遞歸調(diào)用所需保存的信息構(gòu)成運(yùn)行工作棧的一個(gè)工作記錄，在每進(jìn)入下一層遞歸調(diào)用時(shí)，系統(tǒng)就建立一個(gè)新的工作記錄，并把這個(gè)工作記錄進(jìn)棧；每返回一層遞歸調(diào)用，就出棧一個(gè)工作記錄。因?yàn)闂ｍ數(shù)墓ぷ饔涗洷囟ㄊ钱?dāng)前正在運(yùn)行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動(dòng)記錄。共六十頁(yè)執(zhí)行(zhíxíng)情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址其中(qízhōng)，返回地址用行編號(hào)表示nxyz返回地址共六十頁(yè)main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}3ABC03ABC02ACB63ABC02ACB61ABC63ABC02ACB6ABC123ABC共六十頁(yè)main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC0共六十頁(yè)main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0共六十頁(yè)main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0?？?ABC02BAC8共六十頁(yè)遞歸小結(jié)(xiǎojié)優(yōu)點(diǎn)：結(jié)構(gòu)(jiégòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。共六十頁(yè)解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)(běnzhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3、通過(guò)變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)(xiǎojié)共六十頁(yè)練習(xí)(liànxí)使用遞歸的方式把輸入的一行字符逆序打印(dǎyìn)出來(lái)。提示：遇到‘\n’表示一行結(jié)束。共六十頁(yè)練習(xí)(liànxí)給出一種(yīzhǒnɡ)解決方式private

intindex=0;private

char[]chars;public

chargetChar(){if(index<chars.length)returnchars[index++];elsereturn'\n';}public

voidsetChars(char[]c){this.chars=c;}共六十頁(yè)練習(xí)(liànxí)public

voidreverse(){charc=getChar();if(c!='\n'){reverse();System.out.println(c);}}public

static

voidmain(String[]args){Testt=newTest();Scannersc=newScanner(System.in);Stringinput=sc.nextLine();