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)的时间复杂度。 三、顺序查找和字符串的蛮力匹配
顺序查找，再简单不过的查找算法了，算是对蛮力思想的一种应用。以及字符串的蛮力匹配也是这样的。
新闻名称：java凸包代码蛮力法 凸包问题蛮力法代码
网页地址：http://6mz.cn/article/dopgjps.html