程序设计实习 3月份练习解答 2012-3.

Presentation on theme: "程序设计实习 3月份练习解答 2012-3."— Presentation transcript:

1 程序设计实习 3月份练习解答 2012-3

2 POJ普遍问题 Wrong Answer 错误的算法 理解错误 Time Limit Exceeded 程序运行超时 优化程序 改变算法

3 POJ普遍问题2 Output Too Much Runtime Error 程序输出太多 看看你的代码是否有按照题意的要求输入输出和结束
除0 内存非法使用(数组越界，使用指向非法地址的指针)

4 A: 计算对数 描述:给定两个正整数a和b。可以知道一定存在整数x，使得x <= logab < x + 1 输出x
输入:第1行是测试数据的组数n，每组测试数据占2行，分别是a和b。每组测试数据之间有一个空行，每行数据不超过100个字符 输出:n行，每组测试数据有一行输出，也就是对应的x。输入数据保证x不大于20

5 A: 计算对数 描述:给定两个正整数a和b。可以知道一定存在整数x，使得x <= logab < x + 1 输出x
输入:第1行是测试数据的组数n，每组测试数据占2行，分别是a和b。每组测试数据之间有一个空行，每行数据不超过100个字符 输出:n行，每组测试数据有一行输出，也就是对应的x。输入数据保证x不大于20

6

7 同学们的算法 大整数乘法： 对i，依次用a^i与b比较 取大整数前6位,用log函数,转换为logb / loga
这样可以吗？ float占用4字节空间，大致取值范围是(±)10的-38次方到10的38次方，精度是6位有效数字 double占用8字节空间，大致取值范围是(±) 10的-308次方到10的308次方，精度是15位有效数字。

8 float：N=(-1)sx(1+M)x2E-127 （0<E<255）
IEEE 754标准 N=(-1)sx(1+M)x2E-偏移 float：N=(-1)sx(1+M)x2E-127 （0<E<255） double：N=(-1)sx(1+M)x2E-1023 （0<E<2046） E:指数 M:尾数（0~1之间）

9 #include<iostream> #include<cmath> using namespace std; int main() { int n; double a,b; cin>>n; while(n--) cin>>a>>b; cout<<int(log10(b)/log10(a))<<endl; }

10 B:宇航员 描述：宇航员，在他的起始位置现在建立一个虚拟xyz坐标系，称为绝对坐标系，宇航员正面的方向为x轴正方向，头顶方向为z轴正方向，则宇航员的初始状态如下图所示： 现对六个方向分别标号，x，y，z正方向分别为0，1，2，负方向分别为3，4，5；

11 宇航员 任务描述： 　　请根据宇航员对自己在相对方向上移动的描述确定宇航员最终的绝对坐标和面向的绝对方向。对在相对方向上移动的描述及意义如下： forward x 　向前走x米。 back x　先转向后，再走x米。 left x 先转向左，再走x米。 right x 先转向右，再走x米。 up x 先面向上，再走x米。 down x 先面向下，再走x米。 此题是一道模拟题，不难。但是有各种方向需要判断，稍微有点繁琐，不过只要耐心、细心慢慢写条件分支语句，很快就能做出来。有一些小的规律，可以减少代码量。 最重要的一点，人的当前方向需要面向方向和头顶方向两个方向共同决定。

12 宇航员

13 #include<iostream> using namespace std; int x[6], p, head; int turnL[6][6] = {{0,5,1,0,2,4},{2,0,3,5,0,0}, {4,0,0,1,3,0}, {0,2,4,0,5,1},{5,0,0,2,0,3},{1,3,0,4,0,0}}; int turnR[6][6] = {{0,2,4,0,5,1},{5,0,0,2,0,3}, {1,3,0,4,0,0}, {0,5,1,0,2,4},{2,0,3,5,0,0},{4,0,0,1,3,0}};

14 void CalPositon() { char str[20]; int num,temp; cin>>str; cin>>num; switch(str[0]) case 'f': break; case 'b': p=(p+3)%6; case 'l': p=turnL[head][p]; case 'r': p=turnR[head][p]; break; case 'u': temp = p; p=head; head = (temp+3)%6; case 'd': p=(head+3)%6; head = temp; } x[p] += num;

15 int main() { int t; cin>>t; int i; for(i=0; i<t;i++) int z = 5; while(z>=0) x[z] = 0; z--; } p=0; head=2; int k; cin>>k; int j; for(j=0; j<k; j++) CalPositon(); cout<<x[0]-x[3]<<' '<<x[1]-x[4]<<' '<<x[2]-x[5]<<' '<<p<<endl; return 0;

16 另一种模拟方法： 用p，head，left（或者right）三个方向标识当前方向 Left：head不变，p变为left，left变为p的反方向 作业中的问题： 有些同学做的过于繁琐，大片大片的if else，switch 对于这类模拟题的建议： 找规律，把各类情况综合起来 用好数组：turn[6][6][6] turn[head][p][1-6]

17 C：特殊日历计算 有一种特殊的日历法，它的一天和我们现在用的日历法的一天是一样长的。 思路：
传统日历距离 0:0: 的天数 = 新日历天数 10天算一周，10周算一个月，10个月算一年 24*60*60a = 10*100*100b 换算 ==》 新日历秒数 每天有有10个小时，每个小时有100分钟，每分钟有100秒 bool IsLeapYear(int year) (year % 4 == 0 && year % 100 !=0 ) || (year % 400 == 0)

18 D：循环数 *1 = *2 = *3 = *4 = *5 = *6 = 大整数乘法 判断结果是否是循环数

19 F：浮点数加法 题目中输入输出中出现浮点数都有如下的形式： P1P2...Pi.Q1Q2...Qj 对于整数部分，P1P2...Pi是一个非负整数 对于小数部分，Qj不等于0 求2个浮点数相加的和 小数点对齐 修改版的大整数相加 略过小数点

20 F: 数根 思路 需要注意什么？ 10^1000 -> char[1002] 在累加的过程中，始终保持结果为个位数 比如： 987
= 24  6 9 + 8 = 17  8 8 + 7 = 15  6

21 F: 数根 实现 示例代码 char c; int result = 0;
while (cin>>c && c!=‘\n’) { result += (c-’0’); result = result/10 + result%10; } cout << result << endl;

22 G: 武林 大局 需要哪些类？ 武士（一个基类，三个子类） 世界

23 G: 武林 分析 各门派弟子共性： 各门派弟子特性： 属性：内力、武艺、和生命力，攻击力，所处的格子 行为：运动、攻击 状态：是否死亡
运动方式不同 攻击力计算方式不同

24 G: 武林 设计 class Warrior { protected: public: }; int force; // 内力
int skill; // 武艺 int life; // 生命 int row; int col; public: Warrior(); virtual int getDamage(); virtual void moveOneStep(); bool isDead(); };

25 G: 武林 世界： class World { private: int row; int col;
属性：大小、弟子 行为：往里添加一个弟子、运行、输出当前状态 class World { private: int row; int col; Warrior* warriors[1000]; public: World(); void run(); // 开始运行 void addWarrior(Warrior*); void printStatus(); };

26 G: 武林 main函数 main函数干什么事情？ 生成一个World实例 获取输入，传递给World生成Warrior
全部输入完成后，启动World.run()开始运行n步 输出结果 Main函数不需要与Warrior类有直接的联系 26

27 G: 武林 弟子如何运动 以少林弟子为例，少林弟子在同一列不停运动 定义两个方向 运动时 若无法在原方向运动，则反向
rowDirection = 1 colDirection = 0 运动时 newRow = row + rowDirection newCol = col + colDirection 若无法在原方向运动，则反向 rowDirection = - rowDirection colDirection = - colDirection

28 G: 武林 判断是否发生战斗 当有两名不同门派的弟子进入同一个格子时，不会自相残杀；一个格子里三派 弟子都有时一定会发生一次战斗，而且也只有在这种情况下，才会发生战斗。（同派弟子之间当然，大家都会因为害怕别人渔翁得利而不敢出手；而多名同门派弟子也不会联手对付敌人，因为这有悖于武林中崇尚的单打独斗精神，会被人耻笑）

29 G: 武林 判断是否发生战斗 格子里有几个弟子？ 格子里有哪些弟子？ 用数组计数 在新增弟子和弟子运动时，维护格子的计数
扫描全部格子，确定哪些格子有两个弟子 格子里有哪些弟子？ 方法1：对格子(i, j)，扫描所有弟子确定哪两个弟子在(i, j)上 方法2：定义一个格子类，类内用指针指向当前在格子里的弟子 其他方法 获取两个弟子后再判断两者是否属于同一门派 29

30 H:词典 思路 难点 解决办法： 词典中包含不超过100000个词条 词条长度不超过10 不超过100000查询单词
如果逐个查找，最坏情况就要做100000* *10计算 根据经验3000ms内，poj服务器最多可做10^9次运算 解决办法： 二分查找 100000*log（100000）*10

31 H:词典 实现样例1 const int MAXLEN=12; const int MAXNUM=100010;
struct dicEntry{ char a[MAXLEN],b[MAXLEN]; }dic[MAXNUM]; int cmp(const void *x,const void *y) { return strcmp(((dicEntry*)x)->b,((dicEntry*)y)->b); } // 二分查找 dicEntry* myBinSearch(dicEntry* x,dicEntry* dic,int n) int left=0,right=n-1,mid,con; while (left<=right){ mid=(left+right)>>1; if ((con=cmp(x,dic+mid))<0) // 比中间的字符串小，那么范围就缩小到左半边 right=mid-1; else if (con>0) // 比中间的字符串大，那么范围就缩小到右半边 left=mid+1; else return dic+mid; // 没有找到 return NULL;

32 H:词典 实现样例2 int main() { int n=0; while(scanf("%[a-z]%*c",dic[n].a)){
scanf("%[a-z]%*c",dic[n].b); n++; } qsort(dic,n,sizeof(dicEntry),cmp); //排序 getchar(); dicEntry tmp; while (gets(tmp.b)){ // dicEntry *p=(dicEntry *)bsearch(&tmp,dic,n,sizeof(dicEntry),cmp); // bsearch是STL里的，直接调用也可以，实际也是二分查找 dicEntry *p=myBinSearch(&tmp,dic,n); //二分代码示例 if (p!=NULL) cout <<p->a <<endl; else cout <<"eh\n";