月度归档:2015年12月

二分查找

今天继续刷MOOC的《C程序设计进阶》,讲的是之前学过的排序和查找,自己仔细一想貌似好久没打过二分查找了。所以就打了一个。

二分查找就是把一个已经排好序的数组分成大致相等的两部分,然后取a[n/2]与key做比较,如果key=a[n/2],则找到key,算法中止;如果key<a[n/2],则只要在数组a的左半部分继续搜索key,如果key>a[n/2],则只要在数组a的右半部搜索key.那么它的时间复杂度其实就是while循环的次数。

总共有n个元素,渐渐跟下去就是n,n/2,n/4,….n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。由于n/2^k取整后>=1即令n/2^k=1可得k=log2n,(是以2为底,n的对数)。时间复杂度可以认为是O()=O(logn)。

以下是代码(加入了一个选择排序的函数):

[cpp]
#include <stdio.h>
#include <stdlib.h>
void sort(int score[],int n){
int i,j,k,t;
for(i=0;i<n-1;i++){
k=i;
for(j=i;j<n;j++){ if(score[k]>score[j])
k=j;
}
if(k!=j){
t=score[i];
score[i]=score[k];
score[k]=t;
}
}
}
int binary_chop(int score[],int n,int key)
{
int left=0,right=n-1,mid,ret=-1;
while(left<=right){
mid=(left+right)/2;
if(score[mid]==key)
{
ret=mid;
break;
}
else if(score[mid]<key)
left=mid+1;
else
right=mid-1;
}
return ret;
}
int main()
{
int score[10]={0},i,key,ret;
for(i=0;i<10;i++)
scanf("%d",&score[i]);
sort(score,10);
printf("Input key:n");
scanf("%d",&key);
ret=binary_chop(score,10,key);
if(ret==-1)
printf("Not found.n");
else
printf("%d %dn",ret,score[ret]);
return 0;
}
[/cpp]

简单的测试一下代码高亮插件而已

题目内容:

程序读入一个正整数n(0<n<=100000),然后读入n个整数,均为32位下的整数。输出对这个整数排序后的结果,每个整数后面有一个空格。

输入格式:

一个表示个数的正整数n,和n个整数,以空格间隔。

输出格式:

排序后的n的整数,每个整数后面有一个空格。

输入样例:

6 2 23 54 12 6 8

输出样例:

2 6 8 12 23 54

 

如果直接给100000*sizeof(int)的内存无疑很浪费,那就用动态内存申请吧。。。MOOC上的题好水,只是想测试一下自己的代码插件…..

[code lang=”C”]

#include <stdio.h>
#include <stdlib.h>
void sort(int *p,int n)
{
int i,j,t,k;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i;j<n;j++)
if(p[k]>p[j])
k=j;
if(k!=i)
{
t=p[i];
p[i]=p[k];
p[k]=t;
}
}
}
int main()
{
int *p;
int n,i;
scanf("%d",&n);
p=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
scanf("%d",&p[i]);
sort(p,n);
for(i=0;i<n;i++)
printf("%d ",p[i]);
printf("n");
return 0;
}
[/code]

建站历程

想起第一次看到别人的独立博客,应该是段艺学长的,那时候并没有觉得建立独立博客是一件很炫酷的事情,现在也没有。我只是觉得,这的确是学习的一种很好的方式,后来把段艺学长的友链也都看了一遍,发现很多学长都在用这种方式沉淀自己的知识或者吐槽。

当时我就开始留意如何建站,但是后来了解到还需要买域名,买主机等等一系列事务,这对我一个刚刚进入计算机世界的小白来说有点难度(其实主要是我英语不好,买国外看不懂,买国内又嫌备案麻烦)。随后在逛知乎的看到rccoder学长的网站,发现了一些简单的建站方法,他在网站上还推荐了一些好的vps。再后来因为要翻墙结识了paleport,从他那里了解到了如何购买国外域名,第一次知道了狗爹,但当时还没有解决主机的问题,他给我推荐的一些都需要PayPal。而我只有一张穷逼的学生卡办不了PayPal,所以本来想到寒假好好整一整。但是建议一个独立博客的想法,一直在我心头。所以我就先退而求其次,躲到了博客园。但是博客园的界面实在是简陋,对于我这个有点完美主义的人,实在不忍直视。

但是昨天我拿一个下午的时间学习了一些git的内容,并且终于配好了github的环境,然后就follow了一些大神,熟悉了合并分支的一些操作后,我想既然已经完成了一个本来寒假要完成的任务,再加上本人又无心复习,于是我又一次尝试去建立一个独立博客。以下内容估计会打一些广告,但我真的很感谢他们的帮助:

我又一次找到paleport询问狗爹购买域名事宜,得知可以支付宝后,便开始购买域名。可是谁知道狗爹真是坑爹,欺负我看不懂英文,明明一个.com标价20RMB,结账的时候突然又加了很多服务变成90RMB。无奈之下,只好选择了这个域名,一年20RMB,对于一个初学者无疑还是很好的。

接着便通过rccoder学长的博客找到了香港极速动力主机的客服。在此我要推荐一下这个主机商,定价合理实惠,我赶上他们年末活动就花了40RMB,办了一个一年的套餐。然后联系客服小哥,实在是麻烦他了,我们花一个小时才解析域名成功,主要还是因为狗爹的解析有些坑爹。最后在昨天十点多,我的虚拟主机终于装上了WordPress。

今天早上,英语课不上,室友也走了,正合我意,赶快打开电脑安装WordPress的主题和挂件。结果在修改固定链接的时候出了问题:原来WordPress是默认是动态页面,但是我改为.html后变为伪静态页面,但我的虚拟主机那边并没有设置伪静态规则。然后百度加谷歌,明白了需要上传一个.htaccess文件到虚拟主机的根目录下就好。中午一试,搞定!

下午接着搞定代码高亮插件,并成功把博客园的文章搬家到我的小窝,那么就这样迁移成功了吧?

经历了一天折腾,的确可能很没用,并不会让我期末考多考几分,甚至起到反效果。几个室友也不能安静一会地在讨论题目,真是不想说话了。的确,我这种脾气很怪的人需要一个真正独立的小窝写一写自己的东西吧。已经写了一个Abort的静态页面,那么就可以说,kugwzk装修好啦。一年60RMB,估计以后还会更贵,但我会更尽心的维护它。在这里写一写Qzone没法写的东西,love the life!

Get start!