世界经典算法问题交流探讨

wsm · 发表于 2003-4-16 14:48:14

号称3万个皇后，半小时搞定

牛人就是牛人我们当初作图像处理算法最好的一个程序半小时完成导师给的算法看是看不懂不过30秒钟就可以出来数学真的没话说......

superjava · 发表于 2003-4-22 22:40:45

[code:1]/*
* ８皇后问题：
*在第一位老兄的基础上，我对那个java实现稍做修改，添加
*一个计时器计时，时间好象缩短到原来的十分之一，不过不
*能实现n皇后功能，不过我觉得原来那样太慢，20个皇后也要
*跑半天，没多大意义，所以也就无所谓了。
*
*不足之处还请多多指教，谢谢！！！
*
* @author superjava 2003-4-22
*
*/

public class Queen8 {
   int size=8;
   int resultCount=0;
public void compute (  ) {
   int data[] = new int[8];
   for (int i1=0 ; i1<size/2 ; i1++ ) {
         data[0]=i1;
         for (int i2=0 ; i2<size ; i2++ ) {
            data[1]=i2;
            for (int i3=0 ; i3<size ; i3++ ) {
               data[2]=i3;
               for (int i4=0 ; i4<size ; i4++ ) {
                     data[3]=i4;
                     for (int i5=0 ; i5<size ; i5++ ) {
                        data[4]=i5;
                        for (int i6=0 ; i6<size ; i6++ )  {
                           data[5]=i6;
                           for (int i7=0 ; i7<size ; i7++ ) {
                                 data[6]=i7;
                                 for (int i8=0 ; i8<size ; i8++ ) {
                                    data[7]=i8;
                                    if ( test(data) ) {
                                       output( data );
                                    }
                                 }
                           }
                        }
                     }
               }
            }
         }
   }
}

/*
* 测试这种情况皇后的排列是否可行
*
*/
public boolean test( int[] data ) {
   int i,j;
   for ( i=0 ; i<size ; i++ ) {
         for ( j=i+1 ; j<size ; j++ ) {
            // 测试是否在同一排
            if ( data[i] == data[j] )
               return false;
            // 测试是否在一斜线
            if ( (data[i]+i) == (data[j]+j) )
               return false;
            // 测试是否在一反斜线
            if ( (data[i]-i) == (data[j]-j) )
               return false;
         }
   }
   return true;
}

/*
* 输出某种情况下皇后的坐标
*
*/
public void output ( int[] data ) {
   int i;
   System.out.print ( ++resultCount + ": " );
   for ( i=0 ; i<size ; i++ ) {
         System.out.print ( "(" + i + "," + data[i] + ") " );
   }
   System.out.println ();
   //由于正方形的对称性，我们可以只算一半，而把另一半通过对称规则找出来。
   System.out.print ( ++resultCount + ": " );
   for ( i=0 ; i<size ; i++ ) {
         System.out.print ( "(" + i + "," + (7-data[i])+ ") " );
   }
   System.out.println ();
}
public static void main(String args[]) {
   long starTime=0,endTime=0;
   double elapsedTime=0.0;
   starTime = System.currentTimeMillis();
   (new Queen8()).compute(  );
   endTime=System.currentTimeMillis();
   elapsedTime = (endTime-starTime)/1000.0;
   System.out.println(elapsedTime);
}
}[/code:1]

fishcrazy · 发表于 2003-4-28 12:34:42

大家还是把自己看到的经典算法贴出来，不要老是围着皇后打转，又不是国王的说！

或者楼主在抛砖引玉的时候抛的是一块1t的大金砖，把大家都吓坏了？

ShiChao · 发表于 2003-4-28 16:02:16

建议开《算法与数据结构》版，如何？

fishcrazy · 发表于 2003-4-28 16:07:59

支持的人恐怕不多，因为我就不支持，没那个必要

wsm · 发表于 2003-4-28 16:21:20

是啊算法对于大多数的人来说只是数学问题反正我觉得我是不太可能再去深究算法内部的奥秘了（也没有哪个根基）

moonsky · 发表于 2003-4-28 18:14:16

[quote:136cbfa9b6="fishcrazy"]大家还是把自己看到的经典算法贴出来，不要老是围着皇后打转，又不是国王的说！

或者楼主在抛砖引玉的时候抛的是一块1t的大金砖，把大家都吓坏了？[/quote]
有道理，希望大家各抒己见。

moonsky · 发表于 2003-4-28 18:17:01

前几天在网上看到有人提到这样一个问题：
打印类似下面的：
  1    2 3 4 5
16  17  18  19 6
15  24  25  20 7
14  23  22  21 8
13  12  11  10 9

程序：
[code:1]#include<stdio.h>
main()
{
int i,j,n,k,k1,k2,p;
while (1)
{
printf("Please input a num:");
scanf("%d", &n);
if (!n)
return;
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
{
if (i <= n/2)
{
k1 = i;
}
else
k1 = n + 1 - i;
if (j <= n/2)
{
k2 = j;
}
else
k2 = n + 1 - j;

if (k1 <= k2)
k = k1;
else
k = k2;

p = 4 * n * (k - 1) - 4 * (k - 1) * (k - 1);

if (i == k)
{
printf("%3d ", (j + 1 - k) + p);
continue;
}
if (j == k)
{
printf("%3d ", 4 * (n - 2 * (k - 1)) - (i + 1 - k) - 2 + p);
continue;
}

if (j == n + 1 - k)
{
printf("%3d ", n - 2 * (k - 1) + (i - (k - 1)) - 1 + p);
continue;
}
if (i == n + 1 - k)
{
printf("%3d ", 3 * (n - 2 * (k - 1)) - (j - (k - 1)) - 1 + p);
continue;
}
printf(" ?");
continue;
}
printf("\n");
}
}
}[/code:1]

moonsky · 发表于 2003-4-28 18:20:52

[quote:baba9dd024="ShiChao"]建议开《算法与数据结构》版，如何？[/quote]
想法很好，但是似乎作为编程天空的一个重要部分更合适，因为只有不很冷清的板块才能有生命力。

moonsky · 发表于 2003-4-28 18:26:01

[quote:c3fd792b5a="wsm"]是啊算法对于大多数的人来说只是数学问题反正我觉得我是不太可能再去深究算法内部的奥秘了（也没有哪个根基）[/quote]
萝卜青菜，各有所爱，其实程序里面能够有自己设计的一个比较好的算法的话，很有成就感的。

ShiChao · 发表于 2003-4-28 19:13:28

作为《编程天空》的一部分也好，反正效果是一样的

moonsky · 发表于 2003-4-30 20:44:23

下面我从www.linuxforum.net转一些算法过来, 希望能进一步升华大家对算法的热情.
嘻嘻嘻嘻!

moonsky · 发表于 2003-4-30 20:45:46

[code:1]/*
* Shell 排序算法在 1959 年由 D. Shell 发明。
* 也称为递减增量排序算法，各种实现在如何进行递减上有所不同。
* 不稳定，不需要辅助空间。
*/
/*
* Gonnet 算法，发表于 1991 年。
*/
int shellsortGo(int p[],int n)
{
int op=0;
int h,i,j,temp;
for(h=n; h>1; ) {
h=(h<5)?1:(h*5-1)/11;
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Incerpj-Sedgewick 算法，1985 年发表。
*/
int shellsortIS(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
int incs[16] = { /* a1=3,a2=7,a3=16,a4=41,a5=101 */
1391376, /* a1*a2*a3*a4*a5 */
463792, /* a2*a3*a4*a5 */
198768, /* a1*a3*a4*a5 */
86961, /* a1*a2*a4*a5 */
33936, /* a1*a2*a3*a5 */
13776, /* a1*a2*a3*a4 */
4592, /* a2*a3*a4 */
1968, /* a1*a3*a4 */
861, /* a1*a2*a4 */
336, /* a1*a2*a3 */
112, /* a2*a3 */
48, /* a1*a3 */
21, /* a1*a2 */
7, /* a2 */
3, /* a1 */
1
};
for(t=0; t<16; t++) {
h=incs[t];
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Sedgewick 算法，1986 年发表。Knuth 推荐。
*/
int shellsortSe(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
int incs[18] = {
1045505, 587521, 260609, 146305, 64769,
36289, 16001, 8929, 3905, 2161, 929,
505, 209, 109, 41, 19, 5, 1
};
/* if (i%2) h[i]=8*pow(2,i)-6*pow(2,(i+1)/2)+1;
   * else h[i]=9*pow(2,i)-9*pow(2,i/2)+1; */
for (t=0; t<18; t++) {
h=incs[t];
if (h>n/3)
continue;
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Tokuda(徳田尚之)算法。发表于 1992 年。
*/
int shellsortTo(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
int incs[18] = {
1747331, 776591, 345152, 153401, 68178,
30301, 13467, 5985, 2660, 1182, 525,
233, 103, 46, 20, 9, 4, 1
};
/* h[i]=ceil((9*pow(2.25,i)-4)/5) */
for (t=0; t<18; t++) {
h=incs[t];
if (h>n*4/9)
continue;
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Ciura 算法。发表于 2001 年。性能卓越。
*/
int shellsortCi(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
int incs[18] = {
2331004, 1036002, 460445, 204643, 90952,
40423, 17965, 7985, 3549, 1577, 701,
301, 132, 57, 23, 9, 4, 1
};
for (t=0; t<18; t++) {
h=incs[t];
if (h>n*4/9)
continue;
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*******************************************/
/*  下面几个算法有研究价值                */
/*******************************************/
/*
* D. Shell 最初的算法。
*/
int shellsortSh(int p[],int n)
{
int op=0;
int h,i,j,temp;
for(h=n/2; h>0; h=h/2) {
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Lazarus-Frank 算法，1960 年发表。
* 原为在必要时加 1 使所有增量都为奇数, 现修正为减 1。
*/
int shellsortLF(int p[],int n)
{
int op=0;
int h,i,j,temp;
for(h=n/2; h>0; h=h/2) {
if (h%2==0)
h--;
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*--------------------------------------*/
/*
* Hibbard 算法，1963 年发表。
* 1965 年 Papernov-Stasevich 给出了数学证明。
*/
int shellsortHb(int p[],int n)
{
int op=0;
int h,i,j,temp;
for(h=1; h<=n/4; h=h*2+1);
for( ; h>0; h=(h-1)/2) {
/* h = 1, 3, 7, 15, 31 ... 2^i-1 */
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Papernov-Stasevich 算法, 1965? 年发表。
*/
int shellsortPS(int p[],int n)
{
int op=0;
int h,i,j,temp;
for(h=2; h<=n/4; h=h*2-1);
for( ; h>1; ) {
h=(h==3)?1:(h+1)/2;
/* h = 1, 3, 5, 9, 17, 33 ... 2^i+1 */
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Knuth 算法，他建议在 n<1000 时使用。
*/
int shellsortKn(int p[],int n)
{
int op=0;
int h,i,j,temp;
for(h=1; h<=n/9; h=h*3+1);
for( ; h>0; h=h/3) {
/* h = 1, 4, 13, 40, 121, 364... 3*h+1 */
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*--------------------------------------*/
/*
* Pratt 算法，1971 年发表。
* 原为 h=2^p*3^q 现修正为 7^p*8^q。
*/
int shellsortPr(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
int incs[28] = {
262144, 229376, 200704, 175616, 153664, 134456,
117649, 32768, 28672, 25088, 21952, 19208, 16807,
4096, 3584, 3136, 2744, 2401, 512, 448, 392, 343,
64, 56, 49, 8, 7, 1
};
for(t=0; t<28; t++) {
h=incs[t];
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}
/*
* Sedgewick 算法, 1982 年发表。
*/
int shellsortSe82(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
for (t=1; t*t<=n/4; t+=t);
for (h=n/4; t>0; t/=2, h=t*t-(3*t)/2+1) {
/* h = 1, 8, 23, 77, 281, 1073, 4193, 16577,
   * 65921, 262913, 1050113... 4^i+3*2^(i-1)+1 */
for (i=h; i<n; i++) {
temp=p[i];
for (j=i-h; j>=0 && p[j]>temp; j-=h) {
p[j+h]=p[j];
op++;
}
p[j+h]=temp;
op++;
}
}
return op;
}[/code:1]

moonsky · 发表于 2003-4-30 20:47:27

二分法

[code:1]int binarysearch(int p[],int n,
   int value, /* 查找值 */
   int *m) /* 返回的是第一个大于等于查找值的元素
            * 位置和小于查找值的元素个数 */
{
int op=0;
int i=0; /* 头指针前面的元素小于查找值 */
int j=n-1; /* 尾指针和它后面的元素大于等于查找值 */
int k; /* 中间指针 */
if (n==0) { /* 空列表 */
*m=0;
return 0;
}
while (i<j) {
k=(i+j)/2;
if (p[k]<value)
i=k+1;
else
j=k;
op++;
}
/* 头尾指针指向同一个位置 */
if (p[i]>=value) /* 此位置上元素大于等于查找值 */
*m=i;
else /* 全部元素都小于查找值 */
*m=n;
op++;
return op;
}[/code:1]

moonsky · 发表于 2003-4-30 20:49:06

几种简单排序

[code:1]int selectsort(int p[], int n);
int insertsort(int p[],int n);
int appendsort(int p[], int m, int n);
int bubblesort(int p[],int n);
int combsort(int p[], int n);

int bubblesort(int p[], int n)
{
int op=0;
int i, j;
int temp;
int flag=1;

for (j=n-1; flag>0 && j>0; j--) {
flag=0;
for (i=j; i>0; i--) {
if (p[i-1]>p[i]) {
temp=p[i];
p[i]=p[i-1];
p[i-1]=temp;
flag=1;
}
op++;
}
}
return op;
}

int selectsort(int p[], int n)
{
int op=0;
int i, j, max;
int temp;
for (j=n-1; j>0; j--) {
max=j;
temp=p[j];
for(i=j-1; i>=0; i--) {
if (p[i]>temp) {
max=i;
temp=p[i];
}
op++;
}
p[max]=p[j];
p[j]=temp;
op++;
}
return op;
}

int insertsort(int p[],int n)
{
int op=0;
int i,j,temp;
for (j=1; j<n; j++) {
temp=p[j];
for(i=j-1; i>=0 && p[i]>temp; i--) {
p[i+1]=p[i];
op++;
}
p[i+1]=temp;
op++;
}
return op;
}
/*
* 把小列表插入大列表中，要求大列表有序，被其他算法调用。
*/
int appendsort(int p[],
int m, /* 前半部分列表长度和后半部分列表的开始位置 */
int n)
{
int op=0;
int i,j,temp;
if (m>=n)
for(j=m; j<n; j++) {
temp=p[j];
for(i=j-1; i>=0 && p[i]>temp; i--) {
p[i+1]=p[i];
op++;
}
p[i+1]=temp;
op++;
}
else
for(j=m-1; j>=0; j--) {
temp=p[j];
for(i=j-1; i>=0 && p[i]>temp; i--) {
p[i+1]=p[i];
op++;
}
p[i-1]=temp;
op++;
}
return op;
}

/*
* 改进的冒泡排序算法，性能接近堆排序。
* 在 1991 年由 S. Lacey 和 R. Box 发明。
* 据说在特定的重复性输入下有可能衰退成冒泡排序。
*/
int combsort(int p[], int n)
{
int op=0;
int i;
int temp;
int gap=n;
int flag=1;

while (gap>1 || flag!=0) {
flag=0;
gap=(gap==9||gap==10)?11:gap*10/13;
if (gap==0)
gap=1;
for (i=n-1; i-gap>=0; i--) {
if (p[i-gap]>p[i]) {
temp=p[i];
p[i]=p[i-gap];
p[i-gap]=temp;
flag=1;
}
op++;
}
}
return op;
}[/code:1]

		自动登录	找回密码
密码			注册