C或C++的一些题目，多多思考

cainiao

这些题目是我从一个论坛上的{每日一题}的版快里找来的

1 google 的 top coder 的 850 分例题

假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：

如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。

这规则甚是简单，不过有个问题就是同一个 AB 序列，可能有多个字符串都与之相符，比方说序列“ABA”，就有“acdb”、“cadb”等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的 AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。

2 为什么要定义:char (*p)[6],而不是定义:char (*p)[3]

#include

using namespace std;

void main()

{

char (*p)[6];

char a[3][6]={"hello","iam","David"};

for(int i=0;i<3;i++)

{

p=a;

cout<<<" ";

cout<

}

}

为什么要定义:char (*p)[6],而不是定义:char (*p)[3]

cainiao

3 求X的Y次方的最后三位数

求X的Y次方的最后三位数(10 < x, y < 1000)
如13的13次方的最后三位数为253
如15的20次方的最后三位数为625
如67的210次方的最后三位数为449

int LastThree(int x, int y);
输入参数x，y， 返回X的Y次方的最后三位数。
保证输入的数字有效。

4 一首唐诗的编程题

#include
using namespace std;

int main()
{
cout<<"白日依山尽,\n";
return 0;
}

要求：１、输出"白日依山尽
黄河入海流
欲穷千里目
更上一层楼"

2、不能改动main()函数

cainiao

5 现有3*3的九个方格

现有3×3的九个方格，空出中心的方格，将数字1-8随机的放入到其它的8个方格中，数字1不动，其它的数字可以移动，
最终，使所有数字按1-8的顺序顺时针排列外围方格中。移动的规则是：都可以移向横排或竖排相临空着的方格，而且，都可以移向中心空着的方格。
要求计算出移动移动最少的次数。

函数接口： int minMove(int a[]);
其中 a[] 表示从左上角顺时针放入的8个数。

6 编一个能处理简单四则运算的函数。

编一个能处理简单四则运算的函数。为了简单起见，参与运算的数都为int，且只需考虑加法，减法和乘法，不考虑除法，但要考虑括号。
函数接口：
int expr(char a[]);
说明：
数组a[]中保存需要计算的数学表达式，其长度l <= 30。比如
chara[] =“3*(5-4)”;
表达式不会为空，且保证有意义，里面只有阿拉伯数字0~9，+,-,*,(,)，以’\0’结尾，没有空格，括号只有’(‘与’)’，可以嵌套，但肯定成对出现；测试环境为32位平台（若参赛者使用16位编译器，我会用32位编译器重新编译），保证运算过程和结果不会产生溢出；函数返回值为最终计算结果。

cainiao

7 拼音输入法

在PC上模拟实现一个类似手机上的拼音输入法，要求可以显示大部分常用汉字。输入输出为标准输入输出。具体要求如下。

输入：
0-9的数字键，以及上下左右4个键。左作为确定键，右作为取消键。英文字母在数字键上的布局如下：
0 (标点符号)
1 (空格)
2 abc
3 def
4 ghi
5 jkl
6 mno
7 pqrs
8 tuv
9 wxyz

例：如果要输入“文”，就按9、3、6，程序应该显示所有可能的拼音组合，在这里是wen、zen。如果这时候按键盘上的左箭头键，就表示确定，显示部分拼音为"wen"的汉字，如文、问、闻、温、稳等。再次按左就将“文“显示出来了。具体的输出格式看输出部分。

标点符号必须包括以下几个：
，。、：；？！
其它的也可以自己定义。

例：按0再按左显示”，”
按00左显示“。”
以此类推。

按1左显示空格。比如按了以下键：
0左1左00左
那么显示的效果是
， 、

右箭头为取消键，消去当前层次的上一个输入。如“936右"等效于"93"，"936左右”等效于“936”，“936左左右”相当于什么都没输入。

除以上按键外，另外有两个键a、b也可以自定义它们的用法。

输出：
标准输出。模拟手机显示屏。每次按键后输出4行，每行可显示13个汉字。具体显示格式可自行设计。
注意要求每按一个键就重新输出4行，不管那个按键是否会引起显示变化。

8 北京某所高校的一道C++期末考试题

#include

#include

class Power

{

public:

Power(int i){x=i;}

_______________________

protected:

int x;

};

class Squqre:public Power

{

public:

__________________________;

void display()

{cout<<”x=”<

};

class Cube:public Power

{________________________

};

void fun(__________)

{p.display();

}

void main()

{Square squ(2);

Cube cub(3);

fun(squ);

fun(cub);

}

cainiao

9. 100囚犯问题

有100个无期徒刑囚徒，被关在100个独立的小房间，互相无法通信。每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。 一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！ 囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？

10 约瑟夫问题

有n个人围成一圈，1到3开始转圈报名，喊道3的同学出列，问最后剩下原来的几号

cainiao

11 分数变小数

写出一个程序，将一个以N/D的形式的分数转换为它的小数形式，其中N为分子，D为分母。如果它的小数形式存在循环节，要将其用括号括起来。例如：1/3＝．33333……表示为．(3)。又如41/333＝．123123123…表示为．(123)。
一些转化的例子；
1/3＝.(3)
22/4＝4.4
1/7＝.(142857)
3/8＝.375
不限位数，越精确越好。<测试数据结果小数点后不超过1024位>

12 排列自然数

将l、2、3、4、5、6、……N，这N个连续的自然数排成一圈，使每两个相邻数之和都为素数。那么这N最大为多少？编程输出N的值，输出这N个数的排列。
函数接口: char *prime(int &n)
说明: 1、n返回为满足条件最大的自然数，
2、函数返回这n个数的排列，
3、字符串排列1在最前，每两个数用一个空格分割开，例如:1 2 5 8 9。

cainiao

13 单链表反序

将一个单链表反序,只有一个链表头节点head,还有两个指向节点元素类型的指针p和q,不许申请新的节点及指针变量什么的.用c或c++实现算法.

14 从10亿个数中选出最大的一万个。

从10亿个数中选出最大的一万个。

求时间和空间复杂度上最优的算法

cainiao

15 如何定义和实现一个类的成员函数为回调函数？

就是这个简单的问题啦

16 把10个苹果分成三堆，每堆至少1个，应有多少种分法。

cainiao

17 蛇形矩阵

本程序将自然数 1，2，……，N2 按蛇形方式逐个顺序存入 N 阶矩阵。 例如，当 N = 3 和 4 时分别如图 3.1 和图 3.2。

　　　　　　　　　　　　　　　　　　　　　　　7 　13 　14 　16

　　　　　　　　　　　　　　6　 7　 9 　　　　6 　8　　12 　15

　　　　　　　　　　　　　　2 　5 　8 　　　　2 　5　　9　　11

　　　　　　　　　　　　　　1 　3　 4 　　　　1 　3　　4　　10

　　　　　　　　　　　　　　　图3.1 　　　　　　图3.2

从 an0 开始到 a0n 为止（n = N-1）顺序填入自然数，交替地对每一斜列从左上元素向右下元素或从右下元素向左上元素存数。

18 海盗问题

问题描述：
5个海盗抢到了100颗宝石，每一颗都一样大小且价值连城。他们决定这么分：　　
1抽签决定自己的号码（1~5）；　　
2首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按
照他的方案进行分配，否则将被扔进大海喂鲨鱼；　　
3如果1号死后，再由2号提出分配方案，然后剩下的4个人进行表决，当且仅当超
过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼；　　
5依此类推……　　
条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
　　问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？

解题思路:
每个海盗都会想到把前面的人杀死，以便自已获得最大利益，所以他们心里都先有
一个假设轮到自已分配时的最优方案。而总是前者的方案要优于所有后者的方案就
能获得通过，所以这里出现递归关糸式:第一个方案要优于第二个，第二个要优于第
三，第三... ； 那么第一个就要知第二个方案，第二个就要知第三个方案，第三
个。。。；只到最后一个。注意一个特殊情况：假如有人的方案不管怎样都逃不过
被杀，那么他肯定会把投给前一位，以保证自已的存活。

cainiao

19 微软的一道面试题

一个给定的数值由左边开始升位到右边第N位，如
0010<<1 == 0100
或者
0001 0011<<4 == 0011 0000
请用C或者C++或者其他X86上能运行的程序实现。

20 编写一个函数，输入n为偶数时，调用函数求1/2+1/4+...+1/n,

编写一个函数，输入n为偶数时，调用函数求1/2+1/4+...+1/n,当输入n为奇数时，调用函数　　　1/1+1/3+...+1/n(利用指针函数)