算法之简单的插值查找

昨天搞了下二分查找,今天看看它的升级版:插值查找。 插值查找核心思想是尽量将中间值取的更靠近要查找的目标以减少运算次数,而非像二分法那样盲目的取中间值,即: $$mid=left+ \tfrac{(dst-arr[left])}{(arr[right]-arr[left])}*(right-left)$$ 它的缺点与二分法类似,理想情况下时间复杂度为: $$O(log_2 N)$$ int insert_search(int arr[], int dst, int left, int right) { int mid = left + (dst – (arr[left]) / (arr[right] – arr[left])) * (right – left); if (arr[mid] … “算法之简单的插值查找”

Read More

算法之简单的二分查找

二分查找也成为折半查找,理想状态下的时间复杂度为: $$O(log_2 N)$$ 之所以说是理想状态是因为此算法存在一个缺点,即查找对象必须是有序状态下的排列数据。 int binary_search(int arr[], int dst, int left, int right) { int mid = left + (right – left) / 2; if (arr[mid] == dst) return mid; else if (arr[mid] > dst) … “算法之简单的二分查找”

Read More

C的string实现

直接使用云风大神的cstring库即可,我写的垃圾可以扔了。 Update:2015/08/23 作为基本常识,C语言中的字符串是利用char数组实现的,并且通常是以\0结尾。但是可惜的是其中并没有保存一个字符串的长度的信息,因此再拷贝或移动时,要么移动整个char数组大小的数据,要么在判断完\0得出长度后再移动数据。这样用起来是极不方便的。因此再C++的STL中就有了string。

Read More

算法之快排 Quick Sort

首先要说明的是快速排序是递归算法的一种,因此对于内存紧张的机器来说它并非是个好的选择。 而且快速排序是大规模递归的算法,因此它比大部分排序算法都要快一般用于数据个数比较多的情况。尽管可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。 快速排序是C.R.A.Hoare于1962年发明的一种划分交换排序,由于采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 分治法的流程是: 1. 从数列中取出一个数作为基准数。 2. 排序过程中,把比基准数大的数全放到它的右边,小于或等于它的数全放到它的左边。 3. 再对左右区间重复第二步,直到各区间只有一个数。 看起好像很简单,嗯,写起来也很简单。 void quicksort(int arr[],int left,int right){ if(left<right){ int idx=left, sec=right, tmp=arr[left]; while(idx<sec){ while(arr[sec]>=tmp) sec–; if(idx<sec) arr[idx++]=arr[sec]; while(idx<sec && arr[idx]<tmp) idx++; if(idx<sec) arr[sec–]=arr[idx]; } arr[idx] = … “算法之快排 Quick Sort”

Read More

自定义修改Mifare1卡内部数据

M1卡简介: M1卡的规格是1KB,内部有16个数据区,标号0-15,每个数据区有4个存储块,每个块大小是16字节;M1卡的0数据扇区的起始块通常存放厂商的一些固化信息,不可修改;M1卡都有自己的UID,占据32位;M1卡工作频率为13.56MHz,通信速率106Kbps,工作半径位100ms。 现在大部分学校用的水卡都是这种类型的,包括一些小店的会员卡。而且绝大部分都是采用离线方式,数据都会存在卡的芯片上而没进行联网校验,那么作死的机会就来了。 由于是离线,并且是被动读取,因此你可以随意的修改数据而不被发现。网上大部分的改水卡金额的教程也是基于这个而来的。 那么开始前需要准备好工具: 1. 装了Windows的电脑 2. 淘宝上买个proxmark3 3. M1卡 将proxmark3的驱动安装后,插上设备,到设备管理器中查看使用的是第几个COM口。 比如使用的COM 3口,则使用命令行: proxmark3.exe COM3 接着放上自己的M1卡,通过PRNG漏洞Key,输入命令: hf mf mifare 然后就可以获取0扇区的加密码,接着通过此加密码,可以求各个扇区的密码。 比如0扇区加密码是ffffffffffff,则输入命令: hf mf nested 1 0 A ffffffffffff 利用嵌套循环破解剩下的15个扇区加密码,可以在命令最后添加参数d导出破解后的结果。 接着导出破解后卡内数据,输入命令: hf mf dump 1 … “自定义修改Mifare1卡内部数据”

Read More

使用SSH/SCP的压缩传输选项-C

早期网络特别差,比如说在我小时候1999年那会的64K调制解调器拨号上网时代,为了稳定实时的传输通常会启用压缩。 现如今的网络环境下,在一般是不会用到这种选项。但是如果在限速的情况下传输较大文件时,可能还是会用到,比如现在学校给接入网络的学生限速到1Mbps,传个文件真是要了老命。 这种时候为了加快往服务器上传输文件,可以有两种选择: 1. 可用先用tar命令先压缩,传输结束后在解压。 2. 使用SSH/SCP命令自带的压缩选项 -C 在传输的过程中直接压缩,到服务器后自动解压。 很明显,第二种方便多了。 在开启压缩模式下,默认就是调用gzip算法进行压缩,并且这里同样可以设置压缩等级CompressionLevel项,默认是6,最高时9。配置文件默认在/etc/ssh/ssh_config或当前用户的~/.ssh/ssh_config中。

Read More