查找算法 – JAVA編程語言程序開發技術文章

一、查找算法
1、  順序查找:最基本、最簡單的查找方法
2、  二分查找(折半查找):
 
例:HDU2199
 
[java]
package D0705; 
 
import java.util.Scanner; 
import java.lang.Math; 
 
public class HDU2199 { 
//折半查找 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        int n; 
        double y; 
        double low, high, mid = 0; 
        n = sc.nextInt(); 
        while (n– > 0) { 
            y = sc.nextDouble(); 
            low = 0; 
            high = 100; 
            if (y >= getResult(low) && y <= getResult(high)) { 
                while (high – low >= 1e-6) { 
                    mid = (low + high) / 2; 
                    if (y == getResult(mid)) 
                        break; 
                    else if (y < getResult(mid)) { 
                        high = mid-1e-7;//不能寫成high = mid-1e-6 
                    } else { 
                        low = mid+1e-7;//不能寫成low = mid+1e-6 
                    } 
                } 
                System.out.printf("%.4f", mid); 
                System.out.println(); 
            } else { 
                System.out.println("No solution!"); 
            } 
        } 
 
    } 
    private static double getResult(double mid){ 
        double xr; 
        xr = 8 * Math.pow(mid, 4) + 7 * Math.pow(mid, 3) + 2 * mid* mid + 3 * mid + 6; 
        return xr; 
         
    } 
 

 
二分查找中還需要註意一個三分法:
例:HDU2899
 
[java] 
package D0705; 
 
import java.util.Scanner; 
 
public class HDU2899 { 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        int t; 
        double y, high, low, mid, mid2; 
        t = sc.nextInt(); 
        while (t– > 0) { 
            y = sc.nextDouble(); 
            high = 100; 
            low = mid = mid2 = 0; 
            double min = 0;// 最終的最小結果 
            while (high – low >= 1e-6) { 
                mid = (low + high) / 2;// 二分查找 
                mid2 = (mid + low) / 2;// 二分查找中的二分查找(三分法) 
                min = getFx(mid, y); 
                double min2 = getFx(mid2, y); 
                if (min2 > min) {// 如果min2>min則最小值必定落在mid2到high之間, 
                    low = mid2; 
                } else 
                    // 否則,最小值必定落在low到mid之間 
                    high = mid; 
            } 
            System.out.printf("%.4f", min); 
            System.out.println(); 
        } 
 
    } 
 
    private static double getFx(double x, double y) { 
        double fx = 6 * Math.pow(x, 7) + 8 * Math.pow(x, 6) + 7 
                * Math.pow(x, 3) + 5 * Math.pow(x, 2) – y * x; 
        return fx; 
    } 

 
當然還有很多別的查找方法:由於lz水

作者:lhfight

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。