題分析：
成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站建設(shè)、成都網(wǎng)站制作、班戈網(wǎng)絡(luò)推廣、小程序定制開發(fā)、班戈網(wǎng)絡(luò)營銷、班戈企業(yè)策劃、班戈品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供班戈建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com
根據(jù)常識(shí)，我們到店里買東西找錢時(shí)，老板總是先給我們最大面值的，要是不夠再找面值小一點(diǎn)的，直到找滿為止。如果老板都給你找分?jǐn)?shù)的或者幾角的，那你肯定不干，另外，他也可能沒有那么多零碎的錢給你找。其實(shí)這就是一個(gè)典型的貪心選擇問題。
問題的算法設(shè)計(jì)與實(shí)現(xiàn)：
先舉個(gè)例子，假如老板要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數(shù)，為了找給我最少的硬幣數(shù)，那么他是不是該這樣找呢，先看看該找多少個(gè)25分的，誒99／25＝3，好像是3個(gè)，要是4個(gè)的話，我們還得再給老板一個(gè)1分的，我不干，那么老板只能給我3個(gè)25分的拉，由于還少給我24，所以還得給我2個(gè)10分的和4個(gè)1分。
具體實(shí)現(xiàn)
Code:
//找零錢算法//By falcon//輸入：數(shù)組m，依次存放從大到小排列的面值數(shù)，n為需要找的錢數(shù)，單位全部為分//輸出：數(shù)組num，對(duì)照數(shù)組m中的面值存放不同面值的硬幣的個(gè)數(shù)，就找錢方案 public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;ik;i++) { numi=n/mi; n=n%mi; } return num; }
[Ctrl+A Select All]
演示代碼
Code:
public class zhaoqian{ public static void main(String[] args) { int m[]={25,10,5,1}; int n=99; int[] num=new int[m.length]; num=zhaoqian(m,n); System.out.println(n+"的找錢方案："); for(int i=0;im.length;i++) System.out.println(numi+"枚"+mi+"面值"); } public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;ik;i++) { numi=n/mi; n=n%mi; } return num; }}
[Ctrl+A Select All]
演示結(jié)果：
falcon@falcon:~/program/java$ javac zhaoqian.java
falcon@falcon:~/program/java$ java zhaoqian
99的找錢方案：
3枚25面值
2枚10面值
0枚5面值
4枚1面值
第一、你說的那個(gè)東西不叫框架
第二、你用的算法不是多路合并
第三、題目不是讓你合并、是讓你找出最優(yōu)解
解答，我暈這題目有啥解答的啊，你不是自己編的吧，假如合并兩個(gè)有序序列只要m+n-1次比較，那么不單單這兩個(gè)序列各自有序，同時(shí)其中一個(gè)序列任意元素大于另外一個(gè)序列所有元素
那么答案就是按照k的序號(hào)從前想后依次合并啊
public getMin{
public int MinNumber=0;
public int findMax(int[] a){
for(int i=0;ia.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}
public boolean Compare(int a,int b){
public boolean flag=true;
if(ab) flag=flase;
return flag;
}
public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];
int index=0;
for(int i=0;iM.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}
int max = this.findMax(findM);
MinNumber++;
if((Money-max)!=0) {
getMinNumber(M,Money-max)
}
return MinNumber;
}
public int[] Start(){
System.out.println("請(qǐng)輸入查詢組數(shù)");
int group=System.in.read();
int[] M={1,2,5,10,20,50,100};
int[] Result = new Int[group];
int index=0;
while (group-- 0){
System.out.println("請(qǐng)輸入金額");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}
public void print(int[] MinNumber){
for(int i=0;iMinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}
public static void main(String[] args){
new getMin().print(new getMin().Start());
}
沒測(cè)試啊，有問題請(qǐng)勿噴，呵呵
貪心算法: 思路就是對(duì)花到第一個(gè)噴泉距離從近到遠(yuǎn)排序，然后找到另一個(gè)噴泉距離最大的一個(gè)
復(fù)雜度O(n^2)。
import java.util.*;
public class Demo {
static long[][] flowers;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int x1=in.nextInt();
int y1=in.nextInt();
int x2=in.nextInt();
int y2=in.nextInt();
flowers=new long[n][2];
for (int i = 0; i n; i++) {
int x=in.nextInt();
int y=in.nextInt();
flowers[i][0]=dis(x,y,x1,y1);
flowers[i][1]=dis(x,y,x2,y2);
}
Arrays.sort(flowers, (o1, o2) - {
if (o1[0]o2[0])
return -1;
else if (o1[0]==o2[0])
return 0;
else return 1;
});
long temp=0;
long temp2=0;
for (int i = 0; i flowers.length; i++) {
temp=Math.max(temp,flowers[i][1]);
}
for (int i = 0; i flowers.length; i++) {
for (int j = i+1; j flowers.length ; j++) {
if (flowers[j][1]temp2)
temp2=flowers[j][1];
}
temp=Math.min(temp,flowers[i][0]+temp2);
temp2=0;
}
System.out.println(temp);
}
public static long dis(int x,int y,int x1,int y1){
return (long) (x1 - x) *(x1-x)+ (long) (y1 - y) *(y1-y);
}
}
重慶分公司
重慶分公司
