C++面试题集合

只熟悉C,对C++不甚了解啊,但是面试又基本只有C++和Java的。于是乎,整理一下自己遇到的C++面试/笔试题吧

———————————————–我是背景———————————————————————

题目一:一个C++空类建立以后,会产生哪些成员函数?

分析:当时我就只想到了构造和析构函数啊。答案是6个。

[cpp]
class Empty
{
public:
Empty(); // 缺省构造函数
Empty( const Empty&); // 拷贝构造函数
~Empty(); // 析构函数
Empty& operator=( const Empty&); // 赋值运算符
Empty* operator&(); // 取址运算符
const Empty* operator&() const; // 取址运算符 const
};
[/cpp]

但并不一定是6个,如果编译器发现我们只是申明了Empty,并没有发现创建Empty的实例,那么编译器是什么函数都不会生成的。

所有这些只有当被需要才会产生。比如,
Empty e;
编译器就会根据上面的实例,给类Empty生成构造函数和析构函数。
当使用
Empty  e2(e);
编译器就会生成类Empty的拷贝构造函数。
Empty   e3;
e3 = e;
编译器生成赋值运算符函数
Empty    &ee = e;
编译器生成取地址运算符函数。

经过我们的分析可以这样理解:对于一个没有实例化的空类,编译器是不会给它
生成任何函数的,当实例化一个空类后,编译器会根据需要生成相应的函数。这条理论同样
适合非空类(只声明变量,而不声明函数)。

———————————————————————————————————————————–

题目二:STL中,vector与list的区别?

分析:其实基本就是 数组 与 双向链表 的区别,所以就很显然啦。

vector能够很好的支持随机访问,即有下标操作[],但如果要插入或者删除一个数则需要较多次数的移动元素。

list能够很好的支持插入、删除操作,但由于没有下标操作[],所以查找一个元素的时候比较耗时。

———————————————————————————————————————————–

题目三:内联函数、宏的区别?

分析:

由于内联函数首先它是一个函数,所以可以从宏与普通函数的对比入手,先引用一下别人的总结。

(1)、宏只做简单的字符串替换,函数是参数传递,所以必然有参数类型检查(支持各种类型,而不是只有字符串)以及类型转换。
(2)、宏不经计算而直接替换参数,函数调用则是将参数表达式求值再传递给形参。
(3)、宏在编译前(即预编译阶段)进行,先替换再编译。而函数是编译后,在执行时才调用的。宏占编译时间,而函数占执行时间。
(4)、宏参数不占空间,因为只做字符串替换,而函数调用时参数传递是变量之间的传递,形参作为局部变量占内存空间。
(5)、函数调用需要保留现场,然后转入调用函数执行,执行完毕再返回主调函数,这些耗费在宏中是没有的。

使用宏和内联函数都可以节省在函数调用方面的时间和空间开销。二者都是为了提高效率,但是却有着显著的区别:

(1)、内联函数首先是函数,函数的许多性质都适用于内联函数(如内联函数可以重载)。
(2)、在使用时,宏只做简单的文本替换。内联函数可以进行参数类型检查,且具有返回值(也能被强制转换为可转换的合适类型)。
(3)、内联函数可以作为某个类的成员函数,这样可以使用类的保护成员和私有成员。而当一个表达式涉及到类保护成员或私有成员时,宏就不能实现了(无法将this指针放在合适位置)。

———————————————————————————————————————————–

题目四:实现一个算法,删除字符串重复字符

分析:当时笔试面试已经搞了一下午,头晕眼花,第一次还写错了。回来整理了一下,其实很简单。

用两个指针p, q遍历待处理的字符串str,p负责记录有效位,q负责往前扫描。初始化q指向p的下一个字符。

(1) 如果p的字符和q的字符不等,那么由p记录下来,p与q均往前移动一个字符

(2) 如果p的字符和q的字符相等,那么p不动,q往前移动一个字符

代码如下

[cpp]
// the input str must terminated by ‘\0’
char* str_rm_dup(char *str)
{
char *p = str;
char *q = p;

// if str is NULL, then return
if(!p)
return NULL;

/*
* Assign q to the next address of p.
* Before that, we use *q++, not *++q to check whether *p == ‘\0’ in the first loop,
* because if the str is an empty string, str[0] will be ‘\0’.
*/
while(*q++)
if(*p != *q)
*++p = *q;

return str;
}

int main()
{
char a[] = "aabbbccdeeeeee";
printf("%s\n", str_rm_dup(a)); // abcde
return 0;
}
[/cpp]

———————————————————————————————————————————–

题目五:要求写一个没有错误的二分

分析:主要就是注意两点

(1) 整数相加溢出,比如4位机器上,a和b都等于7,即0111,那么相加就悲剧了。

(2) 防止无限循环

代码如下

[cpp]

/*
* Find the index of v if it is in the array of interval [a, b), -1 if not.
* @para a, the first location of the NOT DESC array
* @para l, the lowest index of the interval to be searched
* @para h, the highest index of the interval to be searched
* @para v, the candicate value
* @return index of v, or -1 if not found
*/
int bs(int *a, int l, int h, int v)
{
int m;
while(l < h)
{
m = (unsigned)l + (unsigned)h >> 1; // avoid the overflow of integer
if(a[m] == v)
return m;
if(a[m] < v)
l = m + 1;
else
h = m;
}
return -1;
}

[/cpp]

———————————————————————————————————————————–

题目六:深拷贝、浅拷贝区别?

分析:我的理解就是,浅拷贝只简单赋值,深拷贝是在需要的时候申请新的内存空间。假设我们有一个简单类A,代码如下所示:

[cpp]
class A
{
public:
A(char *s) : str(s) {}
void display()
{
cout << str << endl;
}
public:
char *str;
};
[/cpp]

然后我们写一个简单的main函数来调用它,如下

[cpp]
int main(void)
{
char name[] = "David";

A a(name);
A b = a;

a.display();
b.display();

b.str[0]=’P’;

a.display();
b.display();

return 0;
}
[/cpp]

结果为

QQ图片20131031155933

这是由于我们在类A中并没有去实现拷贝构造函数,编译器则帮我们实现了一个默认的,默认的构造函数则是简单的变量赋值,所以对象a和b的str成员变量其实指向的是同一块儿内存。所以改了一个,另外一个也会跟着改变。

下面我们修改一下类A,代码如下

[cpp]
class A
{
public:
A(char *s) : str(s) {}
void display()
{
cout << str << endl;
}
A(const A &another)
{
str = (char*)malloc(sizeof(char) * (strlen(another.str) + 1));
strcpy(str, another.str);
}
public:
char *str;
};
[/cpp]

然后看运行结果

QQ图片20131031160544

这次对象a和b的str由于指向的不是同一块儿内存地址,所以改了b的str对a不会造成影响。

还有一个区别是,貌似在消除对象a或者b的时候,如果是浅拷贝,会删除两次str所指的内存空间,会造成不可预料的结果。但是我跑程序暂时还未出现崩溃。

———————————————————————————————————————————–

编程之美3.3 计算字符串的相似度 (编辑距离)

Part 1: 题目描述

许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:

1.修改一个字符(如把“a”替换为“b”);

2.增加一个字符(如把“abdd”变为“aebdd”);

3.删除一个字符(如把“travelling”变为“traveling”);

比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度 为1/2=0.5。

给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢?

Part 2:分析

书中给出的解法是通过递归来做的。其实有更快更简便的方法——动态规划。

此题其实就是算法中的求“最短编辑距离”。

编辑距离定义:计算两个字符串的距离,完全相同的字符串距离为0,可以通过修改一个字符、增加一个字符或删除一个字符三种方式来使两个字符串相同,但这些方式会使得距离加1。

假设现在有两个字符串A和B

A:David

B:Taisy

用二维数组d[i][j]表示A中取前i个字符到B中取前j个字符的最短编辑距离。比如d[2][1]就代表从”Da”到”T”的最短编辑距离。这里为2(即把D换成T,去掉A 或者去掉D,把a换成T)。

首先我们作出初始化d[0][j] = j(字符串A子串长度为0,字符串B子串有多少个字符,就作多少次增加操作;于是同理,作删除操作,可得d[i][0] = i)

其中d[i][j]只有3个来源:

1). 来自d[i – i][j – 1],即 “A的前i-1个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离,此时如果A[i] = B[j],则最短编辑距离不变,否则最短编辑距离加1(即把A[i]变为B[j] ),所以d[i][j] = d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1)

2). 来自d[i – 1][j],即 “A的前i-1个字符组成的子串” 到 “B的前j个字符组成的子串” 的编辑距离。此时删除在A的第i个位置上的字符即可,所以d[i][j] = d[i – 1][j] + 1

3). 来自d[i][j – 1], 即 “A的前i个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离。此时在A的子串后面添加一个字符B[j]即可,所以d[i][j] = d[i][j – 1] + 1

于是状态转移方程就写出来啦。

d[i][j] = min (d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1) ,  d[i – 1][j] + 1 ,  d[i][j – 1] + 1)

 

Part 3: 实现代码。

测试代码如下:

[cpp]
#include
#include

using std::cout;
using std::endl;

int min(int a, int b, int c)
{
int small = a;
if(b < small)
small = b;
if(c < small)
small = c;
return small;
}

int main()
{
char s[] = "David_and_Sophia"; // the last character is ‘\0’
char d[] = "Dadiudiu_and_Xiaodiugirl"; // the last character is ‘\0’

int len_s = strlen(s); // 16
int len_d = strlen(d); // 24
int dist[len_s + 1][len_d + 1];

cout << len_s << endl;
cout << len_d << endl;

for(int i = 0; i <= len_s; i++)
dist[i][0] = i;
for(int i = 0; i <= len_d; i++)
dist[0][i] = i;

for(int i = 1; i <= len_s; i++)
for(int j = 1; j <= len_d; j++)
dist[i][j] = min((dist[i – 1][j] + 1), dist[i][j – 1] + 1, dist[i – 1][j – 1] + (s[i – 1] == d[j – 1] ? 0 : 1));

cout << dist[len_s][len_d] << endl;

return 0;
}
[/cpp]

POJ上有对应的题目, POJ 3356,很类似。链接如下,顺带解题参考代码:
http://poj.org/problem?id=3356

AC的代码:

[cpp]
/*
* Author: David
* Date: 2013-9-4 23:27:11
* Brief: edit distance, DP
* Link: http://poj.org/problem?id=3356
*
* POJ info:
* Problem: 3356 User: davidloves
* Memory: 4632K Time: 16MS
* Language: G++ Result: Accepted
*/

#include

#define SIZE 1001

using std::cin;
using std::cout;
using std::endl;

int min(int a, int b, int c)
{
int small = a;
if(small > b)
small = b;
if(small > c)
small = c;
return small;
}

int main()
{
char x[SIZE];
char y[SIZE];
int len_x, len_y;

while((cin >> len_x >> x >> len_y >> y))
{
int dist[len_x + 1][len_y + 1];

for(int i = 0; i <= len_x; i++)
dist[i][0] = i;
for(int j = 0; j <= len_y; j++)
dist[0][j] = j;

for(int i = 1; i <= len_x; i++)
for(int j = 0; j <= len_y; j++)
dist[i][j] = min((dist[i – 1][j] + 1), dist[i][j – 1] + 1, dist[i – 1][j – 1] + (x[i – 1] == y[j – 1] ? 0 : 1));
cout << dist[len_x][len_y] << endl;
}

return 0;
}
[/cpp]

Enjoy!

Ubuntu下Lucene环境搭配

最近想着用一下lucene,就过来简单的写一写,后续还会有。

网上有很多lucene学习资料,例如,lucene源码解析,大家可以去搜一下。这里只是简单介绍怎样搭建lucene所需的环境。

lucene是Apache开源基金会其中一个开源全文检索引擎工具包,是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎。是用Java实现的,所以要想运行lucene就需要搭建JDK环境。

Ubuntu中有自带一个openjdk功能貌似不是很强大,所以果断sun jdk走起~

下面就介绍sun jdk在ubuntu中的安装。其实安装过程是很简单的,错误都是出在环境变量的设置上。

1. 到oracle官网下载linux版本jdk:http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html

我的ubuntu是32位的~

下载的包,名字如下:jdk-7u25-linux-i586.tar.gz

2. 下载完么,就要解压安装,首先在/usr/lib下建一个文件夹名为jvm。然后将压缩包解压至jvm,安装就算完成了~(就是喜欢linux这种不用点来点去的安装,还没有进度条让你抓狂~吼吼~)命令如下:

sudo mkdir -p /usr/lib/jvm/
sudo tar zxvf ~/Downloads/jdk-7u25-linux-i586.tar.gz -C /usr/lib/jvm

jdk1.7.0_25就是我们要用的~

3. 然后就是设置jdk的环境变量,终于来到容易出错的地方了。

网上有很多设置环境变量的方法,让我们来总结一下有哪几种,不过要提醒大家,修改需谨慎有可能什么命令都用不了了呢。最好复制一份出来改。。

3.1 修改/etc/profile文件:

事实证明用这个方法修改之后会对所有的用户生效,如果修改错了,所有的用户在图形界面下都进不去。。

用以下命令修改:

vim /etc/profile

在profile文件中使用:/CLASSPATH命令找到环境变量设置的地方,其实文件就一页那么点,只是想练习一下快捷键。

修改CLASSPATH如下:

 29 JAVA_HOME=/usr/lib/jvm/jdk1.7.0_25
 30 PATH=$JAVA_HOME/bin:$PATH
 31 CLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar
 32 export JAVA_HOME
 33 export PATH
 34 export CLASSPATH

效果如下图:

  • 要注意一个跟windows设置十分不一样的地方,就是CLASSPATH是以“:”冒号来分割的,冒号啊,不要习惯性写成分号~~~

修改之后使用:wq!命令保存退出,不过当然要进行某种操作来让修改生效,这时候就需要source命令了,命令如下:

soure /etc/profile

这就哦拉~我只是说环境变量哦拉~

ERROR,ERROR:

当然如果你不小心改错了的话,ls命令用不了了吧,再想改改profile,什么vi,vim的用不了了吧。那么恭喜你,你悲剧了一小会。不过不要捉急,vi命令和ls命令在/bin里,系统会提示你的,所以进入到/etc下,使用/bin/vi profile打开profile去掉刚才的修改,再source一下就还原了,是不是又正常了呢。。。

不过假设你在改错之后,重启了一下电脑或者想要切换一下用户,恭喜你,你要悲剧一段时间了,因为你登不进去了。。这时,可以在命令行下解决,操作如下:(神奇的linux~)

    1. shift+ctrl+alt+F1进入命令行模式 
    2. 使用root身份登录
    3. cd /etc进入/etc目录
    4.使用/bin/vi profile命令打开profile进行修改
    5.:wq!保存退出
    6.重新登录,问题解决~~

3.2 修改.bashrc文件:

这个与profile的不同之处在于,在所需要的用户目录下修改之后只对该用户有效,也就是出错不会对其他用户造成影响。使用命令如下:

vim /home/username/.bashrc
或者直接 vim ~/.bashrc

打开bashrc文件,在文件末尾找到export,添加以下内容:

106 set JAVA_HOME=/usr/lib/jvm/jdk1.7.0_25
107 export JAVA_HOME
108 set JRE_HOME=${JAVA_HOME}/jre
109 export JRE_HOME
110 set PATH = ${JAVA_HOME}/bin:$PATH
111 export PATH
112 set CLASSPATH =.:${JAVA_HOME}/lib:${JRE_HOME}/lib
113 export CLASSPATH

效果如下图:

然后再使用source ~/.bashrc命令使修改生效

3.3 直接使用shell
用于在Shell下临时使用,换个Shell则无效
export JAVA_HOME=/opt/jdk1.7.0_25
export CLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar
export PATH=$JAVA_HOME/bin:$PATH

4.  修改ubuntu默认jdk版本

修改完环境变量还不可以一劳永逸啊,同学,ubuntu有个自带的openjdk为默认的jdk版本,我们需要用sun jdk代替它。这时就需要用到update-alternatives命令了,首先介绍一下该命令。

update-alternatives是dpkg的实用工具,用来维护系统命令链接符,通过它可以很方便的从很多功能类似的程序和可选配置中设置系统默认使用哪个命令、哪个软件版本,例如,现在我们系统中同时安装了open jdk和sun jdk两个版本,而我们又希望系统默认使用的是sun jdk,那么通过update-alternatives就可以很方便的实现了。

使用以下命令:

sudo update-alternatives --install /usr/bin/java java /usr/lib/jvm/jdk1.7.0_25/bin/java 1062
sudo update-alternatives --install /usr/bin/javac javac /usr/lib/jvm/jdk1.7.0_25/bin/javac 1062
sudo update-alternatives --install /usr/bin/jar jar /usr/lib/jvm/jdk1.7.0_25/bin/jar 1062
sudo update-alternatives --install /usr/bin/javah javah /usr/lib/jvm/jdk1.7.0_25/bin/javah 1062
sudo update-alternatives --install /usr/bin/javap javap /usr/lib/jvm/jdk1.7.0_25/bin/javap 1062

其中1062 为alternative更改后的优先级,新更改的优先级需要大于当前的,通过update-alternatives –display java 可以查看,openjdk的优先级为1061.

然后可以使用以下命令来查看当前jdk版本:

sudo update-alternatives --config java

如下图所示,在selection number处输入0即可(我的显示如此,可能大家显示的不一样,反正只需要将jdk1.7.0_25作为默认版本的即可):

这时sun jdk成为了默认的jdk版本~

如果大家对update-alternatives的其他命令感兴趣,可以搜 一下相关的资料,在这里我们只使用了以上几个命令。

呐,做人呢要开心,现在我们就可以开心一下了,java -version一下吧~

bingo~

报告长官,jdk环境搭建完毕,请下一轮指示~

好的,小的们下面进行大会下一项,lucene安装与设置

二、Lucene的安装与配置

小的们,要用linux啊,安装过程如此简单,妈妈再也不用担心我的学习了~,再也不用对着进度条仰天长叹了~

1. 去Apache下载lucene-4.4.0.tgz: http://www.apache.org/dyn/closer.cgi/lucene/java/4.4.0

2. 解压到/usr/local/src(路径按照自己的习惯来设)下的lucene-4.4.0/中,这就算安装完了ho~

3. 下面要设置一下lucene的环境变量才能用呢。

打开lucene-4.4.0/docs/下的index.html,点击Getting Started中的Lucene demo, its usage, and sources

根据其中的Setting your CLASSPATH提示可知,需要将以下jar包放入路径中:

lucene-core-4.4.0.jar可在lucene-4.4.0/core中找到
lucene-demo-4.4.0.jar可在lucene-4.4.0/demo中找到
lucene-queryparser-4.4.0.jar可在lucene-4.4.0/queryparser中找到
lucene-analyzers-common-4.4.0.jar可在lucene-4.4.0/analysis/commen中找到
我把他们通通放到了lucene-4.4.0/目录中,这样在设置环境变量时就不用打那么多的字了

在这里我们通过修改/etc/profile来设置

将CLASSPATH修改如下图:

然后source /etc/profile使修改生效。

老大,现在可以测试一下lucene是否搭建成功了~

4. 测试:

根据上面文档中Indexing Files的描述以及实际情况,使用以下命令来测试:

java org.apache.lucene.demo.IndexFiles -docs /home/sophia/Documents -index /usr/local/src/lucene-4.4.0/index

其中-docs指定了要索引的文档的位置,-index指定了索引的存放位置。

回车就可以看到如下的效果~:

Selection_021

而index文件中的内容如下:

Selection_022

说明,我们的lucene搭建成功~

再来简单测试一下lucene的搜索功能吧~

使用以下命令:

 java org.apache.lucene.demo.SearchFiles

然后在enter query中输入要搜索的内容,就可以得到包含搜索内容的文档。

hoho~~大王,今天任务已完成,简单的lucene搭建到此结束,接下来的日子,我们就要找一些相关的资料,研究一下lucene是怎样进行搜索的,以及代码实现。敬请期待~

C语言新手入门——从下载IDE开始

c_book

最近,高三的弟弟马上要去大学了。于是乎,打算教一教他C语言。

让我们从下载IDE( Integrated Develop Environment,即集成开发环境)开始。

Step Zero:买书

首先你需要的是一本完美的书,能够随时在你身边指引你的书。

《C程序设计语言》——if not you, then who?

本书原著即为C语言的设计者之一Dennis M.Ritchie和著名计算机科学家Brian W.Kernighan合著的一本介绍C语言的权威经典著作。我想,没有人比他更了解自己的设计。

摒弃你们的“谭浩强”吧~不是说谭先生不好,只是还不够。

Step One:下载最smart的IDE——CodeBlocks

1. 下载

地址:http://www.codeblocks.org/downloads/26

win7系统,选择这个版本就好了codeblocks-12.11mingw-setup.exe,可以从两个站点下载,一般是从这里Sourceforge这里下,如图

QQ图片20130726151625

点击连接以后,会跳到Sourceforge网站,等几秒钟就开始自动下载。

2. 安装

QQ图片20130726152132

点击Next,如上图。

QQ图片20130726152239

点击I Agree, 如上图。

QQ图片20130726152405

这一步是装运行所必须的各种软件,不用修改,默认点击Next就行。如上图。

QQ图片20130726152637

这一步是选择安装路径,可以点击“Browse”然后在弹出的地方选择,或者直接在“Destination Folder”下面的输入框里填写。不建议安装在C盘,工具软件安装在其他盘比较好。比如我就是安装在E盘的Tools文件夹下。然后点击Install进行安装即可。如上图。

如果安装途中出现以下错误,请以管理员身份重新执行安装步骤。即右键“codeblocks-12.11mingw-setup.exe”安装文件,然后选择以管理员身份运行。

QQ图片20130726152954

安装完成后,会问你是否现在运行Codeblocks,如下图。

QQ图片20130726153122

可爱的Codeblocks就出来啦!!!!

3. 编写第一个程序之前的小配置

QQ图片20130726153813

初次启动CodeBlocks的时候,会让你选择是否所有的 C和C++文件都以CodeBlocks打开,如图红色方框所示。点击它,然后点击OK。

现在我们需要新建一个项目,如下图所示。点击界面中间的”Create a new project”

QQ图片20130726154318

在弹出的窗口里选择“Console application“,即控制台程序,如下图所示。

QQ图片20130726154410

点击go,跳到下一个页面。选择使用的语言,这里选C。如下图所示。

QQ图片20130726154736

点击Next以后进入下一个页面。

在”Project title“,即项目名称这里填写项目的名称,这里我们用填入”Test“举例。填好以后,下面的Project fileName以及Resulting fileName会自动帮你填好。

然后就是选择你代码所在的目录,即”Folder to create project in“,可以直接输入文件夹目录(如我的就是放在E盘的Code文件夹下的C文件夹下),也可以点击”…“选择目录。如下图所示。

QQ图片20130726155008

填好以后点击Next,进入下一页。

QQ图片20130726155443

这里是选择编译器(暂时不需要去理解这是什么)以及其他设置。保持默认就好,点击Finish完成项目的配置。

进入开发界面HOHO!!!!

QQ图片20130726155817

双击左边Workspace下的的Sources,即可看到main.c文件,这就是你的源代码文件了,双击main.c,则会在右边的窗口显示出该文件的内容。如下图所示

QQ图片20130726160243

4. 编写人生中的第一个程序

红色框框里的就是啦,假设我现在稍微改一改它,

把printf(“Hello world!\n”);里引号的内容换掉,换成 方脑壳!!!!!!!,即

printf(“方脑壳!!!!!!!\n”);

然后我们要怎么运行这个程序呢?

首先,程序需要编译。因为代码是人写的,写的是一些英文字母,计算机不认识英文字母,它只认0和1,而编译器就是用来干这活儿的,编译器会把人写的代码,”翻译“成计算机能识别的0和1的组合。

那么,CodeBlocks如何编译代码?如下图,点击Build按钮即可。

QQ图片20130726160829

然后会在下方显示编译的结果,可以看到这句话”0 errors, 0 warnings (0 minutes, 0 seconds)“,即表示编译过程没有警告也没有错误。也就是编译器告诉你”我已经成功把你写的代码翻译成0和1的组合了,你可以运行它了“。

然后就是如何运行?

QQ图片20130726161407

如上图所示,点击build旁边的单个绿色箭头,你就会发现系统弹出了一个窗口。而这个窗口的内容就是,看图吧

QQ图片20130726161457

至此,如何新建、编写、编译、运行一个项目以及查看结果讲述完毕,不懂留言。

Step Final:一些建议

学习程序就得发扬”东搞搞,西搞搞“的精神。一般情况下,你是整不坏你的电脑的。所以说,大家多改改这里,改改那里,然后编译运行一下看有什么有趣儿的事情发生。

比如printf里为啥要有双引号啊,我不要行不行?行啊,你去掉以后,再编译,看看结果是什么。

为什么printf以后要有一个分号,我用句号结束行不行?行啊,你改以后,再编译,看看结果是什么。

为什么。。。。

为什么。。。。。

搞就是啊!大不了再改回来。大大不了重新新建一个项目。大大大不了重新安装ColdeBlocks。大大大大大不了重装系统(要是能到这份儿上,,,你已经不得了了)

运行完你的第一个程序以后,试一试把下面这段代码考过去,编译运行一下。

[cpp]
#include <stdio.h>
#include <stdlib.h>

int main()
{
printf("方脑壳!!!!!!!\n");

int a;
int b;
int sum;

printf("请输入两个不大不小的数,正负皆可,用空格隔开吧,回车隔开也可以\n");
scanf("%d%d", &a, &b);
sum = a + b;
printf("其实,计算器的原理就是这么简单,a + b = %d\n", sum);

return 0;
}

[/cpp]

至于有很多语句你现在看不懂,很正常,跟着那本书走吧。不久就会明白的。记住一点,try more and try more and try more……

That‘s all,

Enjoy!

POJ 2453 解题报告

题目意思:给定正整数x,求出在二进制表示中与他有相同个数的‘1’,且比他大的最小的数。

可以把此题当成求二进制中1的个数来做。而该算法在我的其他帖子(点击这里)中已经有详细说明。

代码:

[cpp]
#include <iostream>

using namespace std;

int Count (int);
int main()
{
int x, num;

while(cin >> x)
{
if(!x)
break;
num = Count(x);
while(x++)
if(Count(x) == num)
{
cout << x << endl;
break;
}
}
return 0;
}

int Count(int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

return x;
}
[/cpp]

原题连接http://poj.org/problem?id=2453

寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王”

题目描述:

Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?

首先,我们可以假设有这样一个数据结构来表示帖子

[cpp]
type struct post
{
char* title;
char* content;
int uid;
}post_t;
[/cpp]

题目告诉我们已知所有帖子的列表,也就是说我们知道了所有帖子的链表 post_t* post_list,或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少,并且该uid一定超过了总和的一半。为了叙述方便,下面用数组举例。最容易就想到的方法,就是遍历整个数组,记录每一个uid出现的次数,然后再比较一下,求出最大的。

其实,这个问题就可以等价于:求数组中出现次数大于一半的那个数

解法一

对数组排序,然后遍历排好序的数组,统计各ID出现的次数,找到超过一半的那个即可。代码如下:

[cpp]
int Find (int* post, int len)
{
sort(post, post + len);

int num = 1;
for(int i = 0; i < len; i++)
{
if(post[i] == post[i + 1])
num++;
else
num = 1;
if(num > len / 2)
return post[i];
}
return 0;
}
[/cpp]

这里先调用了一下sort函数排序,也可以换成自己的排序函数。

因为采用了排序,复杂度有所提升,于是书中提出了第二种解法,我觉得是比较巧妙的。

解法二

由于x出现的次数大于总数的一半,所以如果每次删除两个不同的值,不管是否有x,在剩下的数中,x的次数依然会大于总数的一半。

于是,算法可以这样设计

[cpp]
int Find2 (int* post, int len)
{
int x;
int times = 0;
for(int i = 0; i < len; i++)
{
if(times == 0)
{
x = post[i];
times = 1;
}
else
{
if(x == post[i])
times++;
else
times–;
}
}
return x;
}
[/cpp]

该算法不用排序,很巧妙的通过向前移动达到了“删除”的目的,自己真的没想到:)。

越来越觉得优美的代码就是美了,简洁明了,而又功能强大。

扩展问题:

随着Tango的发展,管理员发现,“超级水王”没有了。统计结果表明,有3个发帖很多的ID,他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗?

解法x

这个思路就是一样的了,设a,b,c三人的发帖数都超过了 1/4,那么把4个不同id删除以后,并不影响剩余数组中a,b,c三人的发帖数都超过1/4这个结果。示意图如下所示。

QQ图片20130721232439

把数组分为四个四个数字一组的来看。由于a的发帖数超过了1/4,所以,平均下来,在每一个分组里都有一个a,并且至少在某一组中有大于一个的a,假如分组1中的四个数字都不相同,我们删除分组1,如果a不在分组1里面,那么在剩余的2~n组中,a出现的次数显然会继续大于1/4;如果a在分组1里面,那么在剩余2~n组中,平均下来,a还是会至少在每一个分组出现一次。所以只要分组1中4个数字不相同(主要是保证没有两个a),那么删除分组1,并不改变a在剩余数组中出现次数依然大于1/4的事实。同理b,c。

代码如下:

[cpp]
void Findx(int* post, int len)
{
int a, b, c;
int ta = 0;
int tb = 0;
int tc = 0;

for(int i = 0; i < len; i++)
{
if(ta == 0)
{
a = post[i];
ta++;
}
else if(a == post[i])
ta++;
else if(tb == 0)
{
b = post[i];
tb++;
}
else if(b == post[i])
tb++;
else if(tc == 0)
{
c = post[i];
tc++;
}
else if(c == post[i])
tc++;
else
{
ta–;
tb–;
tc–;
}
}

cout << "a: " << a << "\t";
cout << "b: " << b << "\t";
cout << "c: " << c << "\t";
}
[/cpp]

Enjoy!

求二进制数中1的个数

编程之美第2.1题————求二进制数中1的个数

题目描述:对于一个字节(8bit)的无符号整形变量,求其中的二进制表示中“1”的个数,要求算法的执行效率尽可能的高。

书中由浅入深地给出了几种解法。

解法一

也是最容易想到的,因为对于无符号整数,若采取对2取余操作,结果只有两种,奇数余1,偶数余0,而奇数的二进制最后一位为1,偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果,以二进制数1011和1100举例:

1011 对2取余,余数为1,二进制末尾为1,即含有一个1

1100 对2取余,余数为0,二进制末尾为0,即含有一个0

不管这个二进制数的高位有多少个0或者多少个1,对2取余的操作只与最低位相关。所以,如果能够把所有的位都作为最低位,对2取余一次,然后将结果相加,即可得到该题答案。而二进制数中,右移操作,就相当于除以2,所以有了以下解法。

[c]
unsigned int Count (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end of loop when x is 0
{
if(x % 2 == 1) // to judge whether the last bit is ‘1’
{
num++;
}
x = x / 2; // same as x >> 1
}
return num;
}
[/c]

当然你要是觉得除法耗费时间,可以把x = x / 2改成 x >> 1,本质上是一样的。

解法二

既然提到了右移,就能想到,右移的时候会把最后一位移丢,那我们只要在每一次移动的时候,判断一下最后一位是否为1,然后重复该步骤直到将所有位都移除。用1011举例:
1011,最后一位是1,结果加1,右移一位,变成0101

0101,最后一位是1,结果加1,右移一位,变成0010,

0010,最后一位是0,结果不加,右移一位,变成0001,

0001,最后移位是1,结果加1,右移一位,变成0000,所有位都已移除,结束算法。

而判断最后一位是否为1,可以用&操作,x & 0x1 即可。

算法如下:

[cpp]
unsigned int Count2 (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end the loop when x is 0
{
// x & 0x01 will be 0 if the last bit is ‘0’, otherwise ‘1’
num = num + (x & 0x01);
x = x >> 1; // right shift 1 bit
}
return num;
}
[/cpp]

可以看到,上述两种解法对每一位都进行了比较运算,时间复杂度都为O(log2x),出于降低时间复杂度的角度,书中又给出了第三种解法,让复杂度只与二进制数中‘1’的个数相关。

解法三

该解法确实好玩儿,让我有一种“让广大码农飞,让搞算法的死”的感觉,很巧妙。还是先举一个例子来阐述原理:对于无符号一个二进制数x,与 x – 1 采取&操作会消除x最低位的1,假设x为1010,0000:

x – 1 的二进制为 1001,1111,与x进行&以后得1000,0000,最低位的1没有了,让x = 1000,0000

x – 1 的二进制位 0111,1111,与x进行&作以后得0000,0000,最低位的1没有了,x 为0,结束算法

算法一共就执行了两次,即‘1’的个数。不管‘1’之后有多少个0,x & (x – 1) 总是会消除最低位的1,这就是该算法的巧妙之处了。代码如下。

[cpp]
unsigned int Count3 (unsigned int x)
{
unsigned int num = 0;
while(x)
{
x = x & (x – 1);
num++
}
return num;
}
[/cpp]

算法把时间复杂度降到了O(n),n为二进制中‘1’的个数。应该算是很不错了,关键是很巧妙,灰常好玩儿有木有。

书中还给出了查表法,因为题目是八位的二进制,那么一共也才256个数,完全可以开一个256大小的数组,将结果存起来,如255的二进制为1111,1111,让result[255] = 8,同理把其他所有数的结果都存一遍,以后需要的时候直接返回result[x]就可以了。只是如果不是八位的,变成了32位,那查表这种空间换时间的方法就很不划算了。

后来查阅网上一些题解的时候,发现很多大牛对此题书中解法的提出了质疑。比如解法三,虽然理论上一次地址计算就可以解决,但实际上这里用到一个访存操作,且第一次访存的时候很有可能那个数组不在cache里,这样一个cache miss导致的后果可能就是耗去几十甚至上百个时钟周期(因为要访问内存)。而对于这种数据规模给定,而且很小的情况下,耗去几十甚至上百个时钟周期是很慢的。所以对于这种“小操作”,这个算法的性能其实是很差的。

然后我看到了另外一个巧妙的解法,有点像二分,个人灰常喜欢。

解法X

怎么说呢,先举个例子,比如整数212的二进制1101,0100,一共有4个‘1’对吧。而正好又是8位大小,有没有一种“对折对折再对折”的冲动,有木有?

于是算法可以这样描述:

先把相邻的‘1’的个数算出来,同样二进制的形势保存起来

QQ图片20130720202159

那么现在 10,01,01,00分别代表了1101,0100中相邻两位中‘1’的个数。而且由于是计算的相邻两位,所以‘1’的个数最多为2,所以用两位足够表示。

现在的问题变成了,如何继续处理第一步得到的结果1001,0100呢,对于1001,0100,

第8位,第7位联合起来,即10,表示了原二进制数(1101,0100)中第8位与第7位所含‘1’的个数。

第6位,第5位联合起来,即01,表示了原二进制数(1101,0100)中第6位与第5位所含‘1’的个数。

第4位,第3位联合起来,即01,表示了原二进制数(1101,0100)中第4位与第3位所含‘1’的个数。

第2位,第1位联合起来,即01,表示了原二进制数(1101,0100)中第2位与第1位所含‘1’的个数。

现在我们就需要把新得到的二进制串1001,0100的

8、7联合位与6、5联合位相加,即把10和01相加,代表原第8,7,6,5位的‘1’的个数

(因为8、7联合起来才表示原第8位和原第7位一共有多少个‘1’,这里不能再次分开计算他们了,应该把他们当成一个整体。同理6、5位,也当成一个整体来看待)

4、3联合位与2、1联合位相加,即把01和01相加,代表原第4,3,2,1位的‘1’的个数

QQ图片20130720225843

后面就类似啦,把0011与0001相加,代表原第8,7,6,5,4,3,2,1位的‘1’的个数

QQ图片20130720230443

就得到最后的结果了,结果为4。

好了,现在剩下的问题就是怎么样让相邻的位相加,怎么样让相邻两位的相加,怎么样让相邻四位的相加。

拿相邻两位的相加举例,

(x & 0x55) + (x >> 1  & 0x55)

因为0x55展开成二进制就是0101,0101,观察1的位置,奇数位为1,偶数位为0,这样和x进行与操作的结果就是保留了x的奇数位。然后x右移一位以后,再与0x55进行与操作,对x>>1来说是保留了奇数位,但相对于原来的x则是保留了偶数位。最后将两式相加,就得到了x的二进制中,相邻两位的‘1’的个数。

同理因为0x33展开成二进制是0011,0011,所以相邻二位的相加则为

(x & 0x33) + (x >> 2 &  0x33)

因为0x0f展开成二进制是0000,1111,所以相邻四位的相加则为

(x & 0x0f) + (x >> 4 &  0x0f)

所以算法如下:

[cpp]
unsigned int CountX (unsigned int x)
{
x = (x & 0x55) + (x >> 1 & 0x55);
x = (x & 0x33) + (x >> 2 & 0x33);
x = (x & 0x0f) + (x >> 4 & 0x0f);
return x;
}
[/cpp]

优美的代码总是很简洁,这个算法估计只要十几行指令吧,速度应该是很不错了,至于网上其他更好的算法,写得让我半天看不懂哈哈~~感觉太复杂了也就失去了美。

最后,POJ的相关题目有Problem2453

原题链接:http://poj.org/problem?id=2453

解题报告:http://keping.me/poj2453/

That’s all,

Enjoy!