資訊專欄INFORMATION COLUMN
摘要：由的位置決定乘以幾，依次為，，，，，。遞歸算法遞歸算法就是本次結(jié)果用另外的參數(shù)調(diào)用自己。然而這個(gè)函數(shù)方法本身并沒有用，因?yàn)榉椒ㄖ腥魝鬟f參數(shù)為基本型如，在方法中對(duì)其值的改變并不會(huì)在主函數(shù)中產(chǎn)生影響。
Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
public static int indexOf(int key, int[] a) {
int lo = 0;
int hi = a.length - 1; // 記住要-1
int mid;
while (lo <= hi) { //記住有等號(hào)
mid = (lo + hi) / 2;
if (key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
練習(xí)題
求對(duì)數(shù)
Exe 1.1.14
編寫一個(gè)靜態(tài)方法 lg()， 接受一個(gè)整型參數(shù)N，返回不大于log2(N)的最大整數(shù)。不要使用Math庫。
public static int lg(int N){
// m = log a N
int a=2; //a為底數(shù)
int m=0;
for(;N>1;N/=a){
m++;
}
return m;
}
遞歸乘法/乘方
Exe 1.1.18
乘法
函數(shù)即為乘法的遞歸形式，返回值為a*b
分析：
引入二進(jìn)制例子
2|4……0
2|2……0
2|1……1
4的二進(jìn)制表示為100
eg:3*4
???011
*??100
11000
將b看做二進(jìn)制，當(dāng)b的二進(jìn)制位為1時(shí)，與a相乘。由1的位置決定a乘以幾，依次為1，2，4，8，16，...,2^n。將各個(gè)乘積累加起來。
（類似于十進(jìn)制的乘法運(yùn)算方式，不同位置的乘法依次會(huì)乘以1，10，100，1000，...，10^n，最后累加）
代碼思想：
1.循環(huán)判斷
大循環(huán)
判斷b的二進(jìn)制位是否為1{若是，sum+=a;若不是，不需要做任何操作，因?yàn)榧?不影響}
a=a*2
繼續(xù)看更高一位，直到看完。
return sum。
（類似于綜合法）
public static int multi(int a, int b) {
int isys = 4; //n進(jìn)制
int sum=0; //這個(gè)不能寫在for里面，因?yàn)閒or里面聲明的為局部變量。
for (; b != 0; b /= isys) {
if (b % isys != 0) {
sum += a * (b % isys);
}
a *= isys;
}
return sum;
}
2.遞歸算法
遞歸算法就是return 本次結(jié)果+用另外的參數(shù)調(diào)用自己。
（類似于分析法，抽絲剝繭回去）
public static int multi2(int a, int b)
{
if (b == 0) return 0;
if (b % 2 == 0) return multi(2*a, b/2);
return multi(2*a, b/2) + a;
}
乘方的遞歸形式
public static int power(int a, int b)
{
if (b == 0) return 1;
if (b % 2 == 0) return power(a*a, b/2);
return power(a*a, b/2) * a;
}
交換
用異或的方式交換兩個(gè)變量，不使用第三個(gè)變量，節(jié)省一個(gè)空間。
然而這個(gè)函數(shù)方法本身并沒有用，因?yàn)榉椒ㄖ腥魝鬟f參數(shù)為基本型（如int），在方法中對(duì)其值的改變并不會(huì)在主函數(shù)中產(chǎn)生影響。
public static void exch(int a, int b){
a=a^b;
b=a^b;
a=a^b;
}
待補(bǔ)充
局部變量；全局變量；靜態(tài)變量
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66435.html
摘要：區(qū)別把數(shù)字對(duì)應(yīng)成字符。這個(gè)是字符串的第位。稍作修改可適應(yīng)不等長的字符串。因此增加一個(gè)組別，記錄字符為空的頻次。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 5 Section 1 字符串排序 參考資料http://blog.csdn.net/gua...
摘要：堆中位置的結(jié)點(diǎn)的父節(jié)點(diǎn)的位置為，子節(jié)點(diǎn)的位置分別是和一個(gè)結(jié)論一棵大小為的完全二叉樹的高度為用數(shù)組堆實(shí)現(xiàn)的完全二叉樹是很嚴(yán)格的，但它的靈活性足以使我們高效地實(shí)現(xiàn)優(yōu)先隊(duì)列。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 2 Section 4 優(yōu)先隊(duì)列 ...
摘要：離心率計(jì)算題目釋義計(jì)算點(diǎn)的離心率，圖的直徑，半徑，中心計(jì)算圖的圍長定義點(diǎn)的離心率圖中任意一點(diǎn)，的離心率是圖中其他點(diǎn)到的所有最短路徑中最大值。圖的中心圖中離心率長度等于半徑的點(diǎn)。改動(dòng)離心率計(jì)算，在遍歷中增加的賦值即可。 離心率計(jì)算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...
摘要：在實(shí)際的測(cè)試中，算法的運(yùn)行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點(diǎn)橋的算法也有著很深的聯(lián)系。學(xué)習(xí)該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。 參考資料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...
摘要：算法圖示代碼復(fù)雜度時(shí)間初始化優(yōu)先隊(duì)列，最壞情況次比較每次操作成本次比較，最多還會(huì)多次和次操作，但這些成本相比的增長數(shù)量級(jí)可忽略不計(jì)詳見空間 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 4 Section 3 最小生成樹 定義 樹是特殊的圖 圖的生...
閱讀 1656·2021-09-22 15:21
閱讀 2874·2021-09-09 09:32
閱讀 2705·2021-09-02 09:52
閱讀 3317·2019-08-30 14:02
閱讀 2232·2019-08-26 13:25
閱讀 1464·2019-08-26 13:24
閱讀 1613·2019-08-26 10:31
閱讀 1566·2019-08-26 10:16
