博文
n 皇后问题(2007-05-18 07:23:00)
摘要：/* 问题描叙： 在一个矩阵中布局皇后使所有相邻的皇后既不在同一行
* 也不在同一列和同一对角线上。下面的是以前写的，死算，效率很低。
*/
#include <stdio.h>
#include <math.h>
#include <mem.h>
int test(int i,int j,int n,int *stack) /* 检查位置是否合理 */
{ int m,d;
for(m = 0; m < n; m ++)
{ d = *(stack + m);
if( d == -1)
continue;
else if(d == i || fabs(m - j) == fabs(i - d))
return 1;
}
return 0;
}
void OutToScreen(int *matrix,int npos,int n)
{ int i,j;
printf("\nLayout:%d\n\n",npos);
for(i = 0; i < n; i ++)
{ for(j = 0; j < n; j ++)
{ if( *(matrix + i*n + j) )
printf("%2c",1); /* 头像 */
else printf("%2c",219); /* 小方格 */
}
printf("\n\n");
}
}
&n......
随机算法(2007-04-18 21:21:00)
摘要：随机算法：
呵呵，声明这篇里我们不谈科学的严谨，下面这道题听别人说用DF，DP等，我不知道怎
么DP，DF。因此弄了个随机数，随机分配硬币，当然也要用点小技巧，开始随机次数太
大搞了几次 Time Limit Exceeded，最后恼火了开了 100，我靠 ，这次 Wrong Answer，最后一
次了我搞了个 1000 ，终于 Accepted ！
这主要是在比赛的时候，如果实在没办法做，可以尝试用随机算法，运气好一次就可以
Accepted ，当然也不排除永远不能 Accepted，主要看它的测试数据强不强了。
呵呵，这样太没技术含量了，哪位朋友如果有好的解决办法，贴出来分享下啊 ！
分硬币
一个背包里面最多有100枚硬币，要将这些硬币分给两个人，使得两人得到的钱差距最小
。每枚硬币的面值范围是1分到500分，不允许将一枚硬币分开。
Input
第一行有一个非负整数m（m<=100），表示硬币数。第二行有m个正整数，表示每枚硬币
的面值，中间用空格分开。
Output
每组仅输出一个非负整数，表示两人所分到钱的最小差值。
Sample Input
3
2 3 5
4
1 2 4 6
Sample Output
0
1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define TIMES 1000
int mycmp(const int*a,const int*b){
if(*a > *b)
return 1;
if(*a < *b)
return -1;
return 0;
}
int main(){
int i,j,a[110],asav......
最短路径算法(2007-03-21 09:10:00)
摘要：利用 迪积斯特拉 算法求 " 有向图 " 中某点到其余各点的最短路径
并输出从该点到各点的详细路径,以及总权值。这个程序上学期就写了
今天偶然发现有两个错误，查了我将近两个小时，一个是不可达点的
输出不明显，最大的错误是重复释放了一个指针，我以为是算法错了
从头查到尾，增加了详细的注释，这或者会影响阅读代码，的确，过
多的注释会让代码阅读者不能真正理解代码，当然这也要代码可读性
高。是的代码应该强调，可读性，简洁性，其次才是高效性。
输入: 首先输入图的顶点数 n 边数 m
接着下一行输入源点 sourcePoint
然后输入每一条边的数据包括 起点s，终点e，权值v
包括起点，终点，权值 (顶点从 1 开始编号)
输出: 输出到各点的详细路径以及权值
事例: (建议用管道测试)
输入文件 data.txt 内容如下：
7 12
3
1 2 3&nbs......
完美算法，求子序列和最大(2007-03-20 12:58:00)
摘要：功 能： 在一个整数序列中求一个子序列，该子序列的和最大
输入说明： 首先输入整数序列的长度 length
接着输入该整数序列
输出说明： 输出子序列的起点和终点，并输出该子序列的和
事 例： (建议用管道测试)
输入文件 data.txt 内容如下：
8
12 -13 1 2 23 -14 55 -2
输出：
The subsequence from 2 to 6,max sum is 67 （序......
最快的排序算法(2007-03-20 12:50:00)
摘要：最快的排序算法: 桶 排 序
经分析通过比较的排序算法如,选择排序,插入排序,快速排序,堆排序
等最快为 n*log(n),这是比较排序算法的极限任何通过比较进行排序
的算法都不可能超过这个极限. 现在要介绍的 桶排序 可以超过它为
n ,当然 桶排序 的灵活性却拿不出手,必须要知道待排序数组中最大
的数.下面的程序,首先由用户输入数组的大小,程序随机产生最大数为
不超过 10000 的随机数组,最后输出原始数组,以及排序后的数组.
编译器: VC ++ 6.0 Author : 江南孤峰 Time :2006--10--27
#include <stdio.h>
#include <malloc.h>
#include <memory.h>
#include <stdlib.h>
#include <ctype.h>
int main(){
int order[10000],total,*array,i;
while( 1){
memset(order,0,sizeof(int)*10000);
printf("\nPlease input the size of the array:");
scanf("%d",&total);
array = (int *)malloc(sizeof(int)*total + 4);
printf("Th......
分治法求大数乘(2007-03-20 12:45:00)
摘要：/************************
分治法求大数乘,这种方法是比较好的,听说还有快的算法,我一定可以找到的
思路 : 123 * 456 分治如下
第一次拆分: 12 45 (拆分方法 设 char *a = "123" ,*b = "456" 对 a: t = strlen(a) t/2 得 12(0,1位置) 余者 3(2位置)为
3 6 ( 另一部分,对 b 亦同,即拆分为 45 6,如左)
递归求: 12 * 45 ( 求得 12 * 45 的解果左移两位补0右边,因为其实是 120 * 450 )
12 * 6 ( 同上左移一位其实是120 * 6 )
3 * 45 ( 3 * 450 )
3 * 6 ( 3 * 6 解果不移动 )
第二次拆分(12 * 45 ) ( 如下 )
1 4 ( 交叉相乘并将结果相加 1 * 4 左移两位 400 ,1 * 5 左移一位 50 ,2 * 4 左移一位 80 ,2 * 5 不移为 10)
2 5 ( 相加得400 + 50 + 80 + 10 = 540 )
另外几个不需要拆分 得 72 , 135 , 18 所以: 54000 + 7......
俄罗斯算法求大数乘(2007-03-20 12:29:00)
摘要：/* 俄罗斯式算法求大数乘 */
/* 原理: 举例 ( 9 * 8 ) */
/* (乘数) 9 (被乘数)8 */
/* 4 16 */
/* 2 32 */
/* 1 64 */
/* 将乘数为奇时的被乘数相加 8 + 64 = 72 OK ! */
/* 这钟算法只比传统的好,分治法就比这种要好 */
/* 编译环境: VC ++ 6.0 */
/* Author: 江南孤峰 Time: 2006-10-24 */
#include <stdio.h>
#include <ctype.h>
#define MAX 1000 //存结果的数组大小,乘数较大时需要修改这里
#define MULMAX 100 //存两个乘数的数组大小
void mul(char a[],char b[],int la,int lb);
void divTwo(char a[],int *la);
void add(char a[],char b[],int *la,int *lb);
int input(char a[],char b[],int *la,int *lb);
void mul(char a[],char b[],int length_a,int length_b){
// 求数组 ......
堆排序与快速排序(2007-03-20 11:31:00)
摘要：/***********************************************************************\
功 能：实现两种排序算法，并比较这两种算法
程序首先输出原数组，然后输出经两种算法排序过的数组，并输出
排序时间，数组小排序时间都会显示为 0 ms
编译环境：VC ++ 6.0
author：江南孤峰 data: 2006--6--11
\************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define SIZE 100 //数组大小设置
void Exchange(int *a,int *b){ //交换 *a 与 *b
int t;
t = *a;
*a = *b;
*b = t;
}
void PutOut(int array[]){ //输出排序后的结果
int i,len;
for(i=1,len=array[0]; i<=array[0]; i ++)
printf("%d ",array[i]);
}
void GetRandArray(int array[],int size){ //获取 size 大小的随机数组
int i;
for(i = 1; i <= size; i ++)
array[i] = rand();
a......