基本算法思想Java实现的详细代码

时间:2023-12-28 12:38:02

基本算法思想Java实现的详细代码


算法是一个程序的灵魂,一个好的算法往往可以化繁为简,高效的求解问题。在程序设计中算法是独立于语言的,无论使用哪一种语言都可以使用这些算法,本文笔者将以Java语言为例介绍一些常用的算法思想。

分类

  1. 穷举算法思想
  2. 递推算法思想
  3. 递归算法思想
  4. 分治算法思想
  5. 概率算法思想 

穷举算法思想

穷举算法的基本思想

从所有可能情况中搜索正确答案 
1. 对于一种可能情况,计算其结果。 
2. 判断结果是否满足,如不能满足者执行第一步来搜索下一个可能的情况;如满足则表示选找到一个正确答案。

穷举算法实例

仅有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?

算法实现


int Qiongju(int head,int foot)
{
int i,j,chicken,rabbit;
for(i=0;i<=head;i++)
{
j = head-i;
if(i*2+j*4==foot)
{
chicken = i;
rabbit = j;
return 1;
}
}
return 0;
}

递推算法思想

递推算法基本思想

递推算法是一种理性思维模式的代表,其根据已有的数据和关系,逐步推到而得到结果。对推算法的执行过程:

  1. 根据已知结果和关系,求解中间结果
  2. 判定是否但到要求,若没有继续执行第一步,若有则表示找到一个正确结果 
    递推算法往往需要知道答案和问题之间的实际逻辑关系。再许多数学问题中往往都有着明确的计算公式可以遵循,因此可以采用递推算法来实现。

    递推算法实例

    斐波那契数列:兔子产仔问题 
    题目:如果一对两个月大的兔子以后每个月都可以生一对小兔子,而刚出生的兔子两个月后才可以生小兔子,假定一年内没有兔子死亡事件,那么一年后共有多少对兔子呢?

实现算法

int Fibonacci(int n)
{
int t1,t2;
if(n==1||n==2)
{
return 1;
}
else
{
t1 = Fibonacci(n-1); //递归调用
t2 = Fibonacci(n-2);
return t1 + t2;
}
}

递归算法思想

递归算法即在程序中不反复调用自身达到解决问题的方法,是一个方法在其方法体内调用自身方法调用方式。在递归中主方法又是被调方法。执行递归将反复调用其自身。每调用一层就进入新的一层。 
递归调用分为两种情况:

  • 直接递归,即在方法中调用方法本身
  • 间接递归,即间接地调用一个方法 
    编写递归方法时,必须使用if语句强制在未执行递归前返回。

递归算法实例

递归算法常用于有明显递推性质的问题和一些数学问题。 
问题:求阶乘 
n!=n*(n-1)(n-2)(n-3)………*2*1 
(n-1)!=(n-1)(n-2)(n-3)………*2*1 
得到递推公式: 
n! =n*(n-1)!

算法实现

long fact(int n)
{
if(n<=1)
return 1;
else
return n*fact(n-1);
}

分治算法思想

分治算法基本思想

分治算法就是把一个复杂问题分为规模较小的,计算简单的小问题,然后综合小问题得到最后答案的思想。分治算法执行过程如下:

  1. 对于一个规模为N的问题,若给问题比较容易解决,则直接解决;否则执行下面的步骤。
  2. 将该问题分解为M个规模较小的问题,这些问题相互独立,并且与原问题相互独立。
  3. 递归这些小问题
  4. 然后,将各个小问题合并得到完问题的解

分治算法实例

题目:一个袋子里有三十个硬币,其中有一枚假币,并且假币和真币一某一样,肉眼很难分辨,目前只知道假币比真币轻一点,请问如何区分假币?

算法分析

  1. 首先为每个硬币编号,然后然后将所有硬币等分为两份,放在天平两边。
  2. 再将较轻的那一份等分为两份重复上述方法
  3. 直到剩下两个硬币,较轻的一个就是假币

算法实现

int FalseCoin(int coin[],int low,int high)
{
int i,sum1,sum2,sum3;
int re = 0;
sum1 = sum2 = sum3 = 0;
if(low+1==high)
{
if(coin[low]<coin[high])
{
re = low + 1;
return re;
}
else
{
re = high +1;
return re;
}
}
if((high-low+1)%2==0) //n是偶数
{
for(i=low;i<=low+(high-low)/2;i++)
{
sum1= sum1+coin[i];
}
for(i=low+low+(high-low)/2;i<=high;i++)
{
sum2= sum2+coin[i];
}
if(sum1>sum2)
{
re=FalseCoin(coin,low+(high-low)/2,high);
return re;
}
else if(sum1<sum2)
{
re=FalseCoin(coin,low,low+(high-low)/2);
return re;
}
}
else
{
for(i=low;i<=low+(high-low)/2-1;i++)
{
sum1= sum1+coin[i];
}
for(i=low+low+(high-low)/2+1;i<=high;i++)
{
sum2= sum2+coin[i];
}
sum3=coin[low+(high-low)/2];
if(sum1>sum2)
{
re=FalseCoin(coin,low+(high-low)/2+1,high);
return re;
}
else if(sum1<sum2)
{
re=FalseCoin(coin,low,low+(high-low)/2-1);
return re;
}
else
{
re=low+(high-low)/2+1;
return re;
}
}
return re;
}