黑马程序员技术交流社区
标题: 算法 [打印本页]
作者: GKAirzzzzz 时间: 2017-2-19 12:51
标题: 算法
据说算法也是编程的基础啊~~哈哈，据说是个传说中的高人~算法貌似也蛮多的，分治，贪心，递归，动态规划等等~有一些经典问题。
作者: ZDJ爱TQ 时间: 2017-2-19 13:31
算法！数据库！
作者: GKAirzzzzz 时间: 2017-2-20 22:46
本帖最后由 GKAirzzzzz 于 2017-2-20 22:48 编辑
//背包问题1：在9件物品中选出3件使其质量和与500克之差的绝对值最小。数据由键盘输入。
package com.wh.beibao;
import java.util.Scanner;
public class beibao1 {
public static void main(String[] args){
System.out.println("在9件物品中选出3件使其质量和与500克之差的绝对值最小。数据由键盘输入。");
int p[] = new int[9];//存储用户输入值
Scanner scanner = new Scanner(System.in);
for(int i = 0; i < 9; i++){
p = scanner.nextInt();
}
int I = 0, J = 1, K = 2;//存储选择的物品
int diff = 0;//存储与500的差
int temp = 0;//与diff做比较
diff = Math.abs(500 - p[I] - p[J] -p[K]);
for(int i = 0; i < 7; i++){
for(int j = i+1; j < 8; j++){
for(int k = j+1; k < 9; k++){
temp = Math.abs(500 - p - p[j] -p[k]);
if(temp < diff){
I = i;
J = j;
K = k;
diff = temp;
}
}
}
}
System.out.println("所选元素为：" + p[I] + " , " + p[J] + " , " +p[K]);
System.out.println("差距为:" + diff);
}
}
作者: 阮泰伟 时间: 2017-2-21 01:13
二楼大牛
作者: GKAirzzzzz 时间: 2017-2-21 10:30
本帖最后由 GKAirzzzzz 于 2017-2-21 10:33 编辑
---------------------长文预警--------------------
学习算法设计的重点就是把人类找到的求解问题的方法、步骤，以过程化、形式化、机械化的形式表示出来，以便让计算机执行。我们学习的目标为“用计算机求解问题”。
一、算法的步骤8个步骤如下：
1.问题分析：题目提供了哪些信息，做了哪些假设，要求得到什么结果，是否需要中间结果
2.数学模型建立：适合此问题的数学模型是什么，是否有已解决的类似问题可借鉴
3.算法设计与选择：核心步骤，算法设计的同时要结合数据结构的设计，数据结构的设计简单说就是选取存储方式
4.算法分析：算法分析的目的，首先为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。通常为时间复杂度和空间复杂度。
5.算法表示：对于复杂的问题，确定算法后可以通过图形准确表示算法。算法的表示方式很多如：算法流程图、盒图、PAD图和伪码（类似于程序设计语言）等。
6.算法实现：有哪些变量，变量类型等，它对运算速度和所需内存容量都有很大影响。
7.程序测试：算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。
8.结果整理编制文档：编制文档的目的是让人了解你编写的算法。首先要把代码编写清楚。代码本身就是文档。同时还要采用注释的方式，另外还包括算法的流程图，自顶向下各研制阶段的有关记录，算法的正确性证明（或论述），算法测试结果，对输入/输出的要求及格式的详细描述等。
作者: GKAirzzzzz 时间: 2017-2-21 10:36
二、算法的要素
算法由操作、控制结构、数据结构三要素组成。
1）操作
算术运算：加、减、乘、除
关系比较：大于、小于、等于、不等于
逻辑运算：与、或、非
数据传送：输入、输出, 赋值
2）控制结构 —— 各操作之间的执行次序。
顺序结构：各操作依次执行
选择结构：由条件是否成立来选择 执行
循环结构：有些操作要重复执行，直到功能满足某个条件时结束。又称重复或迭 代结构。
注：模块间的调用也是一种控制结构，特别地模块自身的直接或间接调用—递归结构，是一种功能很强的控制结构。
3）数据结构
算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧密相关的。
算法是把人类找到的求解问题的方法，用以上要素过程化、形式化、机械化地表示出来。
作者: GKAirzzzzz 时间: 2017-2-21 10:41
三、算法的基本性质
目的性 算法有明确的目的，能完成赋予它的功能
分步性 算法为完成其复杂的功能，由一系列计算机可执行的步骤组成
有序性 算法的步骤是有序的，不可随意改变算法步骤的执行顺序
有限性 算法是有限的指令序列，所包含步骤也是有限的
操作性 算法是有限的指令序列，算法所包含的步骤是有限的
四、算法的地位
算法是计算机学科中最具有方法论性质的核心概念，也被誉为计算机学科的灵魂。
五. 算法的基本特征
1.有穷性： 一个算法在执行有穷步之后必须结束。也就是说一个算法它所包含的计算步骤是有限的而且每个步骤都能在有限时间内完成。
2.确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。
3.可行性：算法中描述的操作都可以通过已经实现的基本操作运算有限次实现。
4.算法有零个或多个的输入：有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。
5.算法有一个或多个的输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果。
作者: 黑色旋涡 时间: 2017-2-21 10:44
长文看晕了
作者: GKAirzzzzz 时间: 2017-2-22 21:19
省略了各种图表示，和复杂度计算，直接到循环！
循环设计要点
1．设计中要注意算法的效率
2．“自顶向下”的设计方法
3．由具体到抽象设计循环结构
作者: GKAirzzzzz 时间: 2017-2-22 21:28
本帖最后由 GKAirzzzzz 于 2017-2-22 21:47 编辑
1．循环设计中要注意算法的效率
循环体的特点是：“以不变应万变”。所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。
【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）[sup]n+1[/sup]/(2n-1)! 分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。
数学模型1：Sn=Sn-1+（-1）[sup]n+1[/sup]/(2n-1)!
算法设计1：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为： S=S+（-1）[sup]n+1[/sup]/(2n-1)!
需要用二重循环来完成算法，算法1如下：
[C] 纯文本查看 复制代码
main( )
{int i,n,j,sign=1;
float s,t=1;
input(n);
s=1；
for (i=2;i<=n;i=i+1)
{
t=1; \求阶乘\
for (j=1;j<=2*i-1;j=j+1)
t=t*j;
sign =1; \求（-1）n+1\
for(j=1;j<=i+1;j=j+1)
sign = sign *(-1);
s=s+ sign/t;
}
Print (“Sum=”,s);
}
算法分析：以上算法是二重循环来完成 ，但算法的效率却太低是O（n[sup]2[/sup]）。其原因是，当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结果，用7！*8*9即可得到9！，模型为An=An-1*1/((2*n-2)*(2*n-1)。另外运算sign = sign *(-1);总共也要进行n*(n-1)/2次乘法，这也是没有必要的。下面我们就进行改进。
数学模型2：S[sub]n[/sub]=S[sub]n-1[/sub]+（-1）n+1A[sub]n[/sub]； A[sub]n[/sub]=A[sub]n-1[/sub] *1/((2*n-2)*(2*n-1))
[C] 纯文本查看 复制代码
main( )
{int i,n, sign;
float s,t=1;
Input (n);
s=1；
sign=1;
For (i=2;i<=n;i=i+1)
{sign=-sign;
t= t*(2*i-2)*(2*i-1)};
s=s+ sign/t;
}
Print (“Sum=”,s);
}
算法分析：按照数学模型2，只需一重循环就能解决问题 算法的时间复杂性为O（n）。
作者: GKAirzzzzz 时间: 2017-2-22 21:42
本帖最后由 GKAirzzzzz 于 2017-2-22 21:43 编辑
2．“自顶向下”的设计方法 自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。
【例2】编算法找出1000以内所有完数
例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28 it’s factors are 1，2，4，7，14。
1）这里不是要质因数，所以找到因数后也无需将其从数据中“除掉”。
2）每个因数只记一次，如8的因数为1，2，4而不是1，2，2，2，4。（注：本题限定因数不包括这个数本身）
解答：
1）顶层算法
For (i=0;i<n; i=i++)
{判断i是否是“完数”;
是“完数”则按格式输出；}
2）判断i是否是“完数” 的算法
For (i=2;j<i; j=i++)
{找i的因子，并累加；
如果累加值等于i，是“完数” }
3）进一步细化——判断i是否“完数”算法
s=1
for(j=2;j<i;j=j+1)
if (i mod j=0) (j是i的因子) s=s+j;
if （s=i） i是“完数”;
4）考虑输出格式——判断i是否“完数”算法
考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：
定义数组a，s=1; k=0;
for(j=2;j<i;j=j++)
if (i mod j=0) (j是i的因素)
{s=s+j; a[k]=j;k=k+1;}
if （s=i）
{按格式输出结果}
最终算法：
[C] 纯文本查看 复制代码
main()
{
int i,k,j,s,a[20];
for(i=1;i<=1000;i++)
{
s=1;
k=0; /*两个赋初值语句s=1,k=0一定要位于外部循环的内部*/
for(j=2;j<i;j++)
{
if ((i mod j)==0)
{s=s+j; a[k]=j; k++;}
}
if(i==s)
{
print(s, "it’s factors are :",1);
for(j=0;i<k;j++)
print(",",a[k]);
}
}
}
作者: GKAirzzzzz 时间: 2017-2-22 21:46
3．由具体到抽象设计循环结构对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例题。
【例4】编写算法：打印具有下面规律的图形。
1
5 2
8 6 3
10 9 7 4
算法设计：容易发现图形中自然数在矩阵中排列的规律，题目中1，2，3，4所在位置我们称为第1层（主对角线），例图中5，6，7所在位置我们称为第二层，……。一般地，第一层有n个元素，第二层有n-1个元素……
基于以上数据变化规律，以层号作为外层循环，循环变量为i（范围为1——n）；以层内元素从左上到右下的序号作为内循环，循环变量为j（范围为1——n+1-i）。这样循环的执行过程正好与“摆放”自然数的顺序相同。用一个变量k模拟要“摆放”的数据，下面的问题就是怎么样将数据存储到对应的数组元素。
数组元素的存取，只能是按行、列号操作的。所以下面用由具体到抽象设计循环的“归纳法”，找出数组元素的行号、列号与层号i及层内序号j的关系：
1.每层内元素的列号都与其所在层内的序号j是相同的。因为每层的序号是从第一列开始向右下进行。
2.元素的行与其所在的层号及在层内的序号均有关系,具体地：
第一层行号1——n，行号与j同；
第二层行号2——n，行号比j大1；
第三层行号3——n，行号比j大2；
……
行号起点随层号i增加而增加，层内其它各行的行号又随层内序号j增加而增加，由于编号起始为1，i层第j个数据的列下标为i-1+j。
综合以上分析,i层第 j个数据对应的数组元素是a[i-1+j][j]。
[C] 纯文本查看 复制代码
main( )
{int i,j,a[100][100],n,k;
input(n);
k=1;
for(i=1;i<=n;i=i+1)
for( j=1;j<=n+1-i;j=j+1)
{a[i-1+j][j]=k;
k=k+1;}
for(i=1;i<=n;i=i+1)
{print( “换行符”);
for( j=1;j<=i;j=j+1)
print(a[j]);
}
}
作者: GKAirzzzzz 时间: 2017-3-1 11:37
本帖最后由 GKAirzzzzz 于 2017-3-1 11:56 编辑
快排算法代码[Java] 纯文本查看 复制代码
public class QuickSort {
public static void main(String[] args){
Integer[] list={34,3,53,2,23,7,14,10};
QuickSort qs=new QuickSort();
qs._quickSort(list,0,list.length-1);
for(int i=0;i<list.length;i++){
System.out.print(list+" ");
}
System.out.println();
}
public void _quickSort(Integer[] list, int low, int high) {
if (low < high) {
int middle = getMiddle(list, low, high); //将list数组进行一分为二
System.out.println("Middle:"+middle);
_quickSort(list, low, middle - 1); //对低字表进行递归排序
_quickSort(list, middle + 1, high); //对高字表进行递归排序
}
}
public int getMiddle(Integer[] list, int low, int high) {
int tmp = list[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] >= tmp) {
high--;
}
list[low] = list[high]; //比中轴小的记录移到低端
while (low < high && list[low] <= tmp) {
low++;
}
list[high] = list[low]; //比中轴大的记录移到高端
}
list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}
}
作者: GKAirzzzzz 时间: 2017-3-1 11:38
本帖最后由 GKAirzzzzz 于 2017-3-1 11:39 编辑
把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。原文：http://www.cnblogs.com/xiaoming0601/p/5862860.html
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |