java凸包代码蛮力法 凸包问题蛮力法代码

Java初级编程问题！！！

第一题答案

创新互联建站长期为千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为青海企业提供专业的成都网站设计、成都网站制作，青海网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。

public class Hello{

public static void main(String args[]){

for(int i=9;++i10001;)

if((""+i).equals(new StringBuffer(""+i).reverse()+""))

System.out.print(i+" ");

}}

第二题答案

public class Hello{

public static void main(String args[]){

String s="";

for(int n=10,i=n;--i=0;

System.out.printf("%"+n+"s\b%s\n",s))s+="*";

}}

请问凸包算法的时间复杂度的测试代码怎么写？

代码一

（在编辑器中将"_ "(下划线+空格）替换成两个空格即可编译； 注意要去掉开通的双字节中文空格，蛋疼的百科。）

#include iostream

#include algorithm

using namespace std;

struct point

{

_ _ int x;

_ _ int y;

} p[30005],res[30005];//p标记图中所有的点，res标记凸包上的点

int cmp(point p1,point p2）

{

_ _ return p1.y p2.y || (p1.y == p2.y p1.x p2.x);

}

bool ral(point p1,point p2,point p3） //用叉乘判断点的位置

{

_ _ return (p2.x - p1.x)*(p3.y - p1.y) (p3.x - p1.x)*(p2.y - p1.y);

}

int main()

{

_ _ int n,i;

_ _ while(scanf("%d",n) != EOF) //一共有n个点

_ _ {

_ _ _ _ for(i = 0; i n; i++)

_ _ _ _ _ _ scanf("%d%d",p[i].x,p[i].y);

__ _ _ if(n == 1）

_ _ _ _ {

_ _ _ _ _ _ printf("%d %d\n",p[0].x,p[0].y);

_ _ _ _ _ _ continue;

_ _ _ _ }

_ _ _ _ if(n == 2）

_ _ _ _ {

_ _ _ _ _ _ printf("%d %d\n",p[0].x,p[0].y);

_ _ _ _ _ _ printf("%d %d\n",p[1].x,p[1].y);

_ _ _ _ _ _ continue;

_ _ _ _ }

_ _ _ _ sort(p,p + n,cmp);

_ _ _ _ res[0] = p[0];

_ _ _ _ res[1] = p[1];

_ _ _ _ int top = 1;

_ _ _ _ for(i = 2; i n; i++)

_ _ _ _ {

_ _ _ _ _ _ while(top !ral(res[top],res[top - 1],p[i]))

_ _ _ _ _ _ top--;

_ _ _ _ _ _ res[++top] = p[i];

_ _ _ _ }

_ _ _ _ int len = top;

_ _ _ _ res[++top] = p[n - 2];

_ _ _ _ for(i = n - 3; i = 0; i--)

_ _ _ _ {

_ _ _ _ _ _ while(top != len !ral(res[top],res[top - 1],p[i]))

_ _ _ _ _ _ top--;

_ _ _ _ _ _ res[++top] = p[i];

_ _ _ _ }

_ _ _ _ for(i = 0; i top; i++)

_ _ _ _ _ _ printf("%d %d\n",res[i].x,res[i].y);//输出凸包上的点

_ _ }

_ _ return 0;

}

代码二

#include iostream // 求点集合的凸包的gram算法。n是顶点个数，x,y是顶点

坐标。

#include fstream // order 是按照顶点和左下脚的角度的排序后数组。

#include deque // tu即是逆时针的凸包上的顶点。

#include math.h //

using namespace std; //使用条件：1。点可以任意给，可重复。

// 2。三个以及以上的点。

ifstream fin("input.txt"); // 3。已经考虑了边上有点的情况。

#define NN 1000

#define pi 3.1415827

typedef struct Cseg{

double x,y,tg;

}Cseg;

int n;

double x[NN],y[NN];

deque Cseg order;

deque int tu;

Cseg seg1;

deque Cseg ::iterator p1;

deque int ::iterator p,q;

void in();

void gram();

void makeorder(int s);

double dist(double x1,double yy1,double x2,double yy2）；

double cross(double x1,double yy1,double x2,double yy2）；

void out();

int main()

{

in();

gram();

out();

return 0;

}

void out()

{

int i;

for (i=0;itu.size();i++){

coutorder[tu].x" "order[tu].yendl;

}

couttu.size()" Edges Polydgon"endl;

return;

}

void in()

{

int i;

finn;

for (i=0;in;i++)

finxy;

return;

}

void gram()

{

int i,mm;

mm=0;

for (i=1;in;i++)

if (y[mm]y+1e-9） mm=i;

else if (fabs(y[mm]-y)1e-9 x[mm]x+1e-9） mm=i;

makeorder(mm);

seg1.x=x[mm];

seg1.y=y[mm];

tu.clear();

tu.push_back(0);

tu.push_back⑴；

tu.push_back⑵；

for (i=3;iorder.size();i++){

p=tu.end();

seg1.x=order.x;

seg1.y=order.y;

p--;

q=p-1;

if

（cross(order[*p].x-order[*q].x,order[*p].y-order[*q].y,order.x-order[*

q].x,order.y-order[*q].y)1e-9）

tu.push_back(i);

else{

tu.pop_back();

i--;

continue;

//tu.push_back(i);

}

}//for

return;

}

void makeorder(int s)

{

int i;

double tg;

order.clear();

for (i=0;in;i++){

if (i==s) continue;

tg=atan2(y-y[s],x-x[s]);

seg1.x=x;

seg1.y=y;

seg1.tg=tg;

p1=order.begin();

while (p1!=order.end()){

if (fabs(tg-p1-tg)1e-9）{

if

（dist(x[s],y[s],x,y)dist(x[s],y[s],p1-x,p1-y)+1e-9） {

p1-x=x;

p1-y=y;

}

break;

}

else

if (tgp1-tg){

order.insert(p1,seg1）；

break;

}

p1++;

}//while

if (p1==order.end()) order.insert(p1,seg1）；

}//for

seg1.x=x[s];seg1.y=y[s];

order.insert(order.begin(),seg1）；

//for (i=0;iorder.size();i++)

// printf("i=%d %lf %lf

%lf\n",i,order.x,order.y,order.tg*180/pi);

return;

}

double cross(double x1,double yy1,double x2,double yy2）

{

return (x1*yy2-x2*yy1）；

}

double dist(double x1,double yy1,double x2,double yy2）

{

return pow((x1-x2）*(x1-x2）+(yy1-yy2）*(yy1-yy2），0.5）；

}

代码三

P标程{pku 1113 }

{$Q-,S-,R-}

const

pi=3.1415926575;

zero=1e-6;

maxn=1000;

maxnum=100000000;

var

ans,temp :extended;

n,tot :longint;

x,y :array[0..maxn]of extended;

zz,num :array[0..maxn]of longint;

procedure swap(var ii,jj:extended);

var

t :extended;

begin

t:=ii;ii:=jj;jj:=t;

end;

procedure init;

var

i,j :longint;

begin

readln(n,temp);

for i:=1 to n do readln(x[i],y[i]);

end;

function ok(x,midx,y,midy:extended):longint;

begin

if abs(x-midx)=zero then

begin

if abs(midy-y)=zero then exit(0);

if midyy then exit⑴

else exit⑵；

end

else

begin

if xmidx then exit⑴

else exit⑵；

end;

end;

procedure qsort(head,tail:longint);

var

i,j :longint;

midx,midy :extended;

begin

i:=head;

j:=tail;

midx:=x[(head+tail) div 2];

midy:=y[(head+tail) div 2];

repeat

while ok(x[i],midx,y[i],midy)=1 do inc(i);

while ok(x[j],midx,y[j],midy)=2 do dec(j);

if i=j then

begin

swap(x[i],x[j]);

swap(y[i],y[j]);

inc(i);

dec(j);

end;

until ij;

if itail then qsort(i,tail);

if jhead then qsort(head,j);

end;

function Plot(x1,y1,x2,y2:extended):extended;

begin

Plot:=x1*y2-x2*y1;

end;

function check(first,last,new:longint):boolean;

var

ax,ay,bx,by :extended;

Pt :extended;

begin

ax:=x[last]-x[first];ay:=y[last]-y[first];

bx:=x[new]-x[first];by:=y[new]-y[first];

if Plot(ax,ay,bx,by)-zero then exit(true)

else exit(false);

end;

procedure Tbao;

var

i,j,tail :longint;

begin

tot:=0;

zz[1]:=1;tail:=1;

for i:=2 to n do

begin

while (zz[tail]1）and check(zz[tail-1],zz[tail],i) do dec(tail);

inc(tail);

zz[tail]:=i;

end;

inc(tot,tail-1）；

for i:=1 to tail-1 do

num[i]:=zz[i];

zz[1]:=n;tail:=1;

for i:=n-1 downto 1 do

begin

while (zz[tail]n)and check(zz[tail-1],zz[tail],i) do dec(tail);

inc(tail);

zz[tail]:=i;

end;

for i:=1 to tail-1 do

num[tot+i]:=zz[i];

inc(tot,tail-1）；

end;

function dist(a,b:longint):extended;

begin

dist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));

end;

procedure main;

var

i,j :longint;

begin

qsort（1,n);

Tbao;

ans:=0;

for i:=1 to tot-1 do

ans:=ans+dist(num[i],num[i+1]);

ans:=ans+dist(num[tot],num[1]);

ans:=ans+temp*pi*2;

writeln(ans:0:0);

end;

begin

init;

main;

end.

1005. 继续(3n+1)猜想pat-Java

UVa3n+1问题1.问题描述编号:100.简单描述:就是对一个整数(大于等于1),不断按照这样的规律进行运算,即如果当前数是偶数,则下一个数为当前数除以2,如果当前数为奇数,则下一个数为当前数乘3加1,整个过程直到计算到1为止.那么形成的数列的长度称为cycle-length.问题的输入是:给定一个区间[a,b]问题的输出为:输出给定区间(含端点)所以数的cycle-length的最大的cycle-length.详细描述可参见这里.2.问题分析2.1直观分析最直观的方法当然是采用蛮力法(即brute-force),将给定区间的每个数求出其cycle-length,然后在所以的cycle-length中找出最大的即可.2.2优化优化是建立在分析的基础之上.我们先对一个简单例子进行实验.例如给定区间为B[1,10],即1,2,3,4,5,6,7,8,9,10通过简单分析我们可以知道,通常较大的数具有较大的cycle-length,所以我们可以首先取A=9(为什么不取10,是因为9在一次处理后可变为28,大于10)按照给定的规律来进行如下:928147221134175226134020105168421可以看出,上面红色标记的部分,处于给定的区间内,而且它们的cycle-length显然是小于当前的数9的cycle-length,所以这些数可以从给定的区间内剔除掉,记住当前的cycle-length,于是经过一次的操作后,给定的区间变为3,6继续按照这个方法进行,直至这个区间为空,停止,其中最大的cycle-length即为所求.2.3得出算法算法的描述同2.2处优化部分的分析,具体的算法描述可见3.3.算法描述算法伪代码(类C)描述如下:functiongetMCLB[left,right];//为给定的区间mcl=0;//mcl指max-cycle-lengthwhile!B.empty(){A=getCandidate(B);//这个函数是用来找出B区间内当前最适合处理的元素,//一般是最大的奇数,即预计可能具有较大cycle-length的元素ccl=1;//ccl是指current-cycle-lengthwhile(A!=1){ccl++;A=(A%2)?(3*A+1):(A/2);iffind(B,A)//这个函数是用来判断B区间内是否存在中间结果Apop(B,A);//有则剔除}mcl=(mcl4.具体实现Cpp代码#include"iostream"usingnamespacestd;intgetCandidate(intB[],intbase,intn){inti;for(i=n-1;i=0;i--){if(((base+i)%2)(B[i]==0))returni;}for(i=n-1;i=0;i--){if(!B[i])returni;}return-1;}intnadd2(intleft,intright){intBlength=right-left+1;intlength=Blength;int*B=newint[length];for(inti=0;i0){intccl=1;intpos=getCandidate(B,left,Blength);if(pos==-1)break;B[pos]=1;length--;intA=pos+left;while(A!=1){ccl++;A=(A%2)?(3*A+1):(A/2);intApos;if((A-leftBlength)||(B[A-left])||(Aleftright)cout5.复杂性分析主要的耗时部分是二层循环部分,而外层循环的次数主要取决于内层循环在区间内的命中率.没有进行过统计学的分析,但只要candidate选取合适,每次内层循环会有大于50%的命中率.假设区间内数A的内层循环次数(即由A按照规则变为1的cycle-length)为X,平均命中率为p,那么时间复杂度为:T(n)=X*T(n*(1-p))//其中X为平均的cycle-length6.备注在实现过程中,最初使用的是C++中的vector,但运行时的实际耗时比使用数组的蛮力法还要长,经过分析,这是因为编译器在维护vector这个数据结构时所耗时长是比较大的,特别是当使用vector的earse方法来删除某个特定元素时.所以最后还是使用最基本的数组来实现,用标记来指示删除状态.所以在实际的算法实现中,数据结构的选取也是非常重要的,所谓的程序=算法+数据结构是也.可以改进的地方包括有:getCandidate函数的算法,即如何预估一个具有较长cycle-length的元素;还有当内层循环出现在区间内已标记为删除状态的元素中时,这时内层循环可终止.

蛮力法是什么样的算法？

《算法设计与分析基础》学习 --- 蛮力法 要重温算法思想，并以《算法设计与分析基础》这本书作为教材。该书每一章介绍一种算法设计思想。今天从最简单的开始写起，打好基础。以后再逐步深入，学习更深入的算法。 蛮力法就是一种解决问题的最简单最直观的最容易理解方法，虽然它简单，而且在实际应用中因为效率的原因可能不能派上用场，但是还是不能忽略它。正如书中作者所说，在解决小规模问题的时候也不失为一个方法，而且也是更复杂算法的基础。 一、选择排序

以最简单的思路解决排序问题，对于N个元素的数组，通过N次扫描数组，每次选择出最小的元素放置到正确的位置，N趟扫描后即完成排序。 show sourceview source print? 01/* 02 蛮力法-选择排序 03 将输入数组排成非递减数组 04 05 array:待排数组 06 n:数组大小，即[0,n-1] 07*/08void SelectionSort(int array[],unsigned int n) 09{ 10 int min; 11 for(int i=0;in-1;i++) 12 { 13 min=i; 14 for(int j=i+1;jn;j++) 15 { 16 if(array[j]array[min]) 17 min = j; 18 } 19 if(i!=min) 20 { 21 int temp = array[i]; 22 array[i] = array[min]; 23 array[min] = temp; 24 } 25 } 26}//SelectionSort

这是一个最差的排序方法，对于任何输入都是 O(n*n)的时间复杂度。但是它的最大优点就是交换次数最少。 二、冒泡排序

又是一个经典的蛮力排序算法。这里我仅仅对原始的冒泡做了点点改进，如果算法已经排好序的话该算法扫描一遍便完成排序。

show sourceview source print? 01/* 02 蛮力法-冒泡排序(稍微改进版) 03 将输入数组排成非递减数组 04 05 array:待排数组 06 n:数组大小，即[0,n-1] 07*/08void BubbleSort(int array[],unsigned int n) 09{ 10 int i=n-1; 11 int last; 12 while(i0) 13 { 14 last = 0; 15 for(int j=0;ji;j++) 16 { 17 if(array[j]array[j+1]) 18 { 19 int temp = array[j]; 20 array[j] = array[j+1]; 21 array[j+1] = temp; 22 23 last = j; //记录最近一次交换值的位置 24 } 25 } 26 i = last; 27 } 28}//BubbleSort

但是在最差的情况下，它还是O(n*n)的时间复杂度。 三、顺序查找和字符串的蛮力匹配

顺序查找，再简单不过的查找算法了，算是对蛮力思想的一种应用。以及字符串的蛮力匹配也是这样的。