- 博客(72)
- 资源 (1)
- 收藏
- 关注
原创 计算机中的数
二进制数计算机中,数以二进制的方式存储。二进制整数二进制整数转换为十进制数记 B=bjbj−1⋅⋅⋅b2b1b02B=bjbj−1···b2b1b02B=b_jb_{j-1}···b_2b_1b_{0_2} 则其对应的十进制数为 N=bj×2j+bj−1×2j−1+⋅⋅⋅+b1×21+b0×20N=bj×2j+bj−1×2j−1+···+b1×21+b0×20N=b_...
2018-07-10 15:43:49 1366
原创 第一章 事件的概率
概率是什么衡量某种情况(事件)出现的可能性大小的一种指标。主观概率见书P002试验与事件概率论中事件的含义,分3点在P003到P004,包括试验的含义,随机事件,必然事件,不可能事件的含义。古典概率古典概率的定义:设一个试验有NNN个等可能的结果,而事件E恰好包含其中的MMM个结果,则事件EEE的概率,记为P(E)P(E)P(E),定义为 P(E)=M/NP(E...
2018-07-03 11:42:46 900
原创 AAA前言
说明: 该分类为陈希孺教授所著《概率论与数理统计》笔记,全部内容可见陈教授所著的2009年2月第一版。本书阅读需要少量初等微积分以及矩阵的知识。...
2018-07-02 15:57:54 255
原创 算法导论(第三版)第二章 算法基础
2.1插入排序开篇首先介绍了插入排序,插入排序伪代码如下:INSERTION-SORT(A) for j = 2 to A.length key = A[j] // Insert A[j] into the sorted sequence A[1..j-1] i = j - 1 while i > 0 and A[
2018-02-07 01:23:18 536 1
原创 算法导论(第三版)第一章 算法在计算过程中的作用
本章首先给出了算法的定义,即任何良定义的过程,该过程取某个值或者值的集合作为输入并产生某个值或者值的集合作为输出。 然后举出了一些算法可解决问题的例子,比较有意思,也可以拓宽知识面。提出了NP完全问题。 接着又简要说明了算法的效率问题。 本章习题没什么重要的。 本章作为一个引入,简要介绍了算法,并大概阐述了本书中主要内容。
2018-02-06 23:46:44 370
原创 光亮度方面易混的术语
光强(luminous intensity):发光强度,单位坎德拉(cd),是单位面积的功率流量(通量)。 光通量(luminous flux):人眼所能感觉到的辐射功率,观察者从光源感受到的能量,单位流明(lm),是单位时间内某一波段内的辐射能量与该波段的相对视见率的乘积。 由于人眼对不同波长的光的视见函数不同,所以不同的波长的光的辐射功率即使相等,其光通量并不相等。 光亮度(lumina
2018-01-29 19:13:31 847
原创 算法导论10.3-4:紧凑的双向链表
题目: 我们往往希望双向链表的所有元素在存储器中保持紧凑,例如,在多数组表示中,占用前m个下标位置。(在页式虚拟存储的计算环境下,即为这种情况。)假设除指向聊表本身的指针外没有其他指针指向该链表元素,试说明如何实现过程ALLOCATE-OBJECT和FREE-OBJECT,使得该表保持紧凑。(提示:使用栈的数组实现。) 解答: 在某位大牛的算法导论中的答案中,分配链表元素位置时从数组最前向最后
2017-08-28 11:46:28 966
原创 静态双向链表的多数组实现
使用静态多数组实现链表,结构体及相关函数声明如下:typedef struct ITEM { int key; void * statellite;} item_t;typedef struct STATIC_DOUBLE_ARRAY_DOUBLE_LINKED_LIST{ int size; int count; int head; int f
2017-08-27 22:50:30 931
原创 算法导论10.2-8
题目: 说明如何在每个元素仅使用一个指针x.np(而不是通常的两个指针next和prev)的情况下实现双向链表。假设所有的指针的值都可视为k位的整数,且定义x.np=x.next XOR x.prev,即x.next和x.prev的位异或。(Nil的值用0来表示)注意要说明要获取的表头所需的信息,并说明如何在该表上实现SEARCH、INSERT和DELETE操作,以及如何在O(1)时间内实现该表的
2017-08-27 00:26:33 1272
原创 算法导论10.2-7:单链表的逆转
题目: 给出一个Θ(n)\Theta(n)时间的非递归过程,实现对一个含n个元素的单链表的逆转。要求除存储链表本身空间之外,该过程只能使用固定大小的存储空间。 解答: 使用之前实现的单链表进行操作,C语言实现如下:int single_linked_list_reverse(SLL * L) { if (L->head == NULL) { fprintf(stderr
2017-08-26 17:33:30 431
原创 链表(Linked List)的C语言实现
链表中的各对象按线性顺序排列,而其顺序是由各个对象里的指针所决定的。 链表有多种形式,它可以是单链接的或者双链接的,可以是已排序的或未排序的,可以是循环的或非循环的。 定义的结构体以及函数如下:typedef struct ITEM { int key; void * statellite;} item_t;typedef struct NODE{ struct N
2017-08-20 23:40:38 7027
原创 队列(Queue)的C语言实现
队列的实现是一种先进先出的策略。以下使用动态分配内存的数组来实现一个队列。其中,队列的resize过程将不会保留原来队列中的item。//Item.htypedef struct ITEM { int key; void * statellite;} item_t;//Queue.h#ifndef STDIO_H#define STDIO_H#include <stdio.
2017-08-18 23:41:36 23225
原创 基数排序
基数排序的说明基数排序是一种用在卡片排序机上的算法。基数排序先按最低有效位进行稳定的排序,再利用排序子算法的稳定性,逐渐对高位进行稳定的排序,依次类推。基数排序必须保证子排序算法的稳定性,伪代码如下:RADIX-SORT(A, d) for i = 1 to d use a stable sort to sort array A on digit i
2017-08-16 15:16:34 766
原创 计数排序
计数排序假设n个输入元素中每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)k=O(n)时,排序的运行时间为Θ(n)\Theta(n)。 计数排序的基本思想是:对每一个输入元素x,确定小于x的元素的个数。利用这一信息直接将x放到它在输出数组中的位置上。 计数排序的伪代码如下: 假设输入是一个数组A[1..n],A.length = n,还需要两个数组,B[1..n]用来存放排
2017-08-15 23:04:42 605
原创 去除尾递归的快速排序以及快速排序的栈深度
对于栈深度的定义: 编译器通常使用栈来存储递归执行过程中的相关信息,包括每次递归调用的参数等。最新调用的信息存在栈的顶部,而第一次调用的信息存在栈的底部。当一个过程被调用时,其相关信息被压如栈中,当它结束时,其信息被弹出。栈深度是在一次计算中会用到的栈空间的最大值。 对于快速排序,假设数组参数的传递是用指针来指示的,所以每次过程调用只需要O(1)的栈空间。 去除尾递归的快速排序伪代码如下:TA
2017-08-14 21:33:13 2681 1
原创 针对相同元素值的快速排序
如果数组中的元素值都相同,随机化的快速排序的运行时间将为O(n2)O(n^2)。 因此,可以考虑对PARTITION过程进行优化。使新的PARTITION排列数组A[p..r]的元素,返回值是两个数组的下标q和t,其中p≤q≤t≤rp \le q \le t \le r,且有: 1. A[q..t]中所有的元素都相同 2. A[p..q-1]中的每个元素都小于A[q] 3. A[t+1..r
2017-08-14 17:05:07 5105
转载 快速排序的最早划分方法:Hoare划分
快速排序的划分过程最早由C.R.Hoare设计,伪代码如下:HOARE-PARTITION(A,p,r)x=A[p]i=p-1j=r+1while TRUE repeat j=j-1 until A[j]<=x repeat i=i+1 until A[i]>=x if i < j exchange A[
2017-08-12 16:00:25 2014 1
原创 快速排序的C语言实现
快速排序主要过程如下: 分解:数组A[p..r]被划分为两个(可能为空的)子数列A[p..q-1]和A[q+1..r],使得A[p..q-1]中元素都小于等于A[q],A[q+1..r]中元素都大于A[q]。 解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]进行排序。 合并:因为子数组都是原址排序,所以不需要合并,数组A[p..r]已经有序。 非随机化版本的快速排序
2017-08-10 23:17:01 1421
原创 算法导论5.1-3
假设你希望以1/2概率输出0和1。你可以自由使用一个输出0和1的过程BIASED-RANDOM。它以概率p输出1,概率1-p输出0,其中0<p<1,但是p的值未知。请给出一个利用BIASED-RANDOM作为子程序的算法,返回一个无偏的结果,能以概率1/2返回0,以概率1/2返回1。作为p的函数,该算法的期望运行时间是多少。
2017-07-20 19:20:58 790 1
原创 算法导论5.1-2
请描述RANDOM(a,b)过程的一种实现,它只调用RANDOM(0,1),该函数以等可能返回0或者1。作为a和b的函数,你的过程的期望运行时间是多少。
2017-07-19 22:39:03 807
原创 算法导论2.3-7
Question description:give a O(nlgn) time algorithm for determining if there exist two elements in an set S whose sum is exact some value x
2017-07-17 21:39:22 681
原创 两个n位二进制整数相加问题
(原问题见算法导论第三版2.1-4) 问题:考虑把两个n位二进制数加起来的问题。这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个(n + 1)元数组C中。
2017-07-17 21:32:41 1739
原创 生产者消费者问题的pthread模拟
操作系统概念第七版上第六章的项目“生产者-消费者问题”的解答。 采用了三个信号量:empty(记录多少个空位),full(记录有多少满位)以及mutex(二进制信号量以保护对缓冲的插入与删除操作)。
2017-07-16 16:54:35 2631 2
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人