- 算法包括三部分：算法思想 + 排序算法 + 查找算法
算法思想：
算法思想 就是 解題思路呻率。
常見的解題思路有如下：
1）窮舉算法思想：為了解決問題和解決問題
2）遞推算法思想：根據(jù)已知結(jié)果和關系捣炬，求解盗棵。適合在有明顯數(shù)學公式的情況下
3）遞歸算法思想：在程序中不斷重復調(diào)用自身來達到求解的目地啡邑。 如求階乘問題
4）分治算法思想：大問題分解成小問題
5）概率算法思想：根據(jù)概率統(tǒng)計的思路求近似值
- 窮舉算法：
/**
* Created by malei on 2016/12/4.
* 1）窮舉算法思想：為了解決問題和解決問題
*/
public class a_窮舉算法 {
/**
* 籠子里有雞和兔北滥，從上面說有35個頭胞四，下面共有94個腳恬汁，求雞和兔的各自數(shù)量
*/
public static void main(String[] args){
qiongju(35,94);
}
/**
* chook + rabbit = head;
* chook*2 + rabbit*4 = foot;
*/
private static void qiongju(int head, int foot) {
for (int chook = 0 ; chook <= head ; chook++){
if((chook*2 + (head - chook)*4) == foot){
Log.show("雞的個數(shù)："+chook +" 兔子的個數(shù)："+(head-chook));
}
}
}
}
- 遞推算法：
/**
* Created by malei on 2016/12/4.
* 遞推算法思想：根據(jù)已知結(jié)果和關系，求解辜伟。適合在有明顯數(shù)學公式的情況下
*/
public class b_遞推算法 {
/**
* 一對兩個月大的兔子以后每一個都可以生一對小兔子氓侧，而一對新生的兔子出生兩個月
* 以后，才能生小兔子游昼。也就是說1月份出生甘苍，3月份才可以產(chǎn)仔。沒有兔子死亡的情況下烘豌，‘
* 一年后共有多少只兔子载庭？
*/
public static void main(String[] args){
int count = opreate(12);
Log.show(count);
}
/**
* 第一個月 ：1
* 第二個月：1
* 第三個月：2
* 第四個月：3
* 第五個月：5
* 已知結(jié)果和關系：每個月都是前兩個月的相加 f(n) = f(n-1)+f(n-2)
*/
private static int opreate(int count) {
if(count <=2 ){
return 1;
}
int total = 0;
total = opreate(count-1)+opreate(count-2);
return total;
}
}
- 遞歸算法
/**
* Created by malei on 2016/12/4.
* 遞歸算法思想：在程序中不斷重復調(diào)用自身來達到求解的目地。 如求階乘問題
*/
public class c_遞歸算法 {
/**
* 求解從1到100相乘的結(jié)果
* @param args
*/
public static void main(String[] args){
long count = opreate(12);
Log.show(count+"");
}
/**
* n! = 1*2*3*...n 因此通過階乘公式：
* n!= n*(n-1)!
* 這里有個坑顽铸，階乘的返回值可能具體超過int的范圍
*/
private static long opreate(int num) {
if(num <= 1 ){
return 1;
}
return num * opreate(num-1);
}
}
- 分治算法
/**
* Created by malei on 2016/12/4.
* 分治算法思想：大問題分解成小問題
*/
public class d_分治算法 {
/**
* 30個硬幣星压，其中有一個是假幣，假幣比真幣輕竣贪，求什么辦法可以找到假幣演怎？
* 硬幣是有編號的
*/
public static void main(String[] args){
int[] coins = {2,2,1,2,2,2,2,2,2};
int count = opreate(coins,0,coins.length-1);
Log.show(count+"");
}
/**
* 解題思路:把錢分兩堆，比較輕重畏纲，輕的在分。票灰。屑迂。
*/
private static int opreate(int[] coins, int low, int high) {
int sum1=0; //前半段和
int sum2=0; //后半段和
//僅剩下兩個進行比較了
if(low+1 == high){
if(coins[low] > coins[high]){
return high;
}else{
return low;
}
}
//個數(shù)為偶數(shù)
if((high+1 - low) % 2 == 0){
//前半段的和
for (int i =0;i<= (low+(high-low))/2 ; i++){
sum1 += coins[i];
}
//后半段的和
for(int i= (low+(high-low))/2+1 ; i <= high ; i++){
sum2 += coins[i];
}
//前后半段的比較
if(sum1 > sum2){
//前段大
//小的繼續(xù)循環(huán)
return opreate(coins,(low+(high-low))/2+1,high);
}else{
//后端大
return opreate(coins,low,(low+(high-low))/2);
}
}else {
//個數(shù)問奇數(shù)時
//前半段和
for (int i = low; i<(low+(high-low))/2-1 ; i++){
sum1 += coins[i];
}
//后半段和
for (int i = low; i<(low+(high-low))/2+1 ; i++){
sum2 += coins[i];
}
//前后相等手报，中間值問題
if(sum1 == sum2){
return (low+(high-low))/2+1;
}
//前后兩段進行比較
if(sum1 >sum2){
//前段大
//小的繼續(xù)循環(huán)
return opreate(coins,(low+(high-low))/2+1,high);
}else {
return opreate(coins,low,(low+(high-low))/2-1);
}
}
}
}
