dcbaicaitang的专栏

原创 第2次实验——算法基本功与综合思考

（1）算法基本功——快速排序     对文件 largeW.txt（下载链接）中的数据，应用快速排序算法进行排序，并与冒泡排序、归并排序进行时间比较。体验算法复杂度对设计算法的影响。 代码如下：   import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; impo

原创 第1次实验——NPC问题(回溯算法、聚类分析)

1）八皇后及N皇后问题     八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发

原创 第七周作业1-------背包问题

（1）背包问题。对上文中提到的背包问题提供的表1（数据文件下载Knapsack.txt，第一行为背包总重量15，物品数量5；第2-6行，分别为第1-5件物品的重量与价值），W=15，编程计算最终背包所装物品的编号、总重量与总价值。要求能够把构造的二维表格输出到文件KnapsackResult.txt中。博文标题：第7周作业1——背包问题。 代码实现如下：

原创 第五周作业——有向图邻接表表示及反向图构造

算法遍历有向图邻接表反向图构造 1. 有向图中反向图构造。对tinyDG.txt（http://pan.baidu.com/s/1o6jWtcA）文件所表示的图，输出其邻接表表示 与 反向图的邻接表表示。类名：GraphReverse。博文标题：第五周作业——有向图邻接表表示及反向图构造 邻接表表示示例如下： 0:1 5 1: 2:0 3 ……

原创 第四周作业-----图的表示

1. 图的表示：给定图数据文件（tinyG.txt），计算得到图的邻接矩阵，并把邻接矩阵保存到文件（tinyG_matrix.txt）中。类名：GraphRepresentation。摘自《Algorithms, 4th Edition》P522。博文标题：第四周作业——图的表示

原创 第三周作业 --------顺序查找和二分查找

2. 查找。Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。     二分查找方法原型：int BSearch(int array[], int low, int high, int target )， array——含有若干整数的数组，low 与 high——查找的起始、结束下标，target—

原创 第三周作业

package com.suanfa; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IO

原创 第六周作业1——利用哈夫曼编码英文字母表

下面给出某文集中字母出现的频率

原创 随机生成一个n bit位的长整数（第二周作业2.2）

2.2： 随机生成一个n bit位的长整数。函数签名如下     long createRndInteger(int n)     输入：随机数bit位的长度为n（解释：3bit位，则最大为111，最小为100；n bit位，则该数字二进制长度为n）     输出：返回该随机数public static long createRndInterger(int n) { //n bit整数

原创 判断一个正整数是否为质数的算法（第二周作业2.1）

使用Miller-Rabin素性测试来判断一个数是否为素数 源代码如下： public static int isPrime(long a) { for(int i=0;i<100;i++) { //u的取值范围为1<u<a,本算法是Miller-Rabin素性检测，如果u=1,将会使得所有的a对于u^(a-1)=1(mod a)都成立 long u=(long)Mat

原创 辗转相除法求最大公约数c++

int gcd(int a,int b){ int temp; if(b>a) { temp=a; a=b; b=temp; } while((temp=a%b)!=0) { if(temp>b) { a=temp; }else { a=b; b=temp; } } return temp;}

原创 算法概论思维导图