算法笔试题_2 .

给定一个N进制正整数，把它的各位数字上数字倒过来排列组成一个新数，然后与原数相加，如果是回文数则停止，如果不是，则重复这个操作，直到和为回文数为止。

如果N超过10，使用英文字母来表示那些大于9的数码。例如对16进制数来说，用A表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。

例如：10进制87则有：

STEP1: 87+78=165

STEP2: 165+561=726

STEP3: 726+627=1353

STEP4: 1353+3531=4884

编写一个程序，输入N(2<=N<=16)进制数M（1<=M<=30000(10进制)）,输出最少经过几步可以得到回文数。如果在30步以内（含30步）不可能得到回文数，则输出0。输入的数保证不为回文数。

【输入】

第一行一个整数L，代表输入数据的组数。

接下来L行，每行两个整数N,M

【输出】

输出L行，对于每个数据组，按题目要求输出结果，并占一行。

【样例输入】

10 87

2 110

【样例输出】

B题恺撒的规划
【问题描述】

　　亚特兰蒂斯是一块富饶美丽的土地。恺撒大帝率领他的大军，经过了一整年的浴血奋战，终于将它纳入了罗马帝国的版图。然而，长期的战火彻底抹去了这里的繁华，昔日的富庶之地如今一片荒芜。恺撒大帝作为一位有着雄才大略的君主，决心在战争的废墟上建起一座更为宏伟的城市。所以，在建城之前，他需要对整个城市进行规划。

　　亚特兰蒂斯是一块矩形平原，恺撒准备在上面修建一些建筑。为了规划方便，他将矩形划分成N*M格。棘手的是，部分古老的神庙残存下来，散布在某些格子内。亚特兰蒂斯的原住民原本就十分信奉神灵，而这些经过战火洗礼的神庙更是被他们视为圣物，是万万不能拆除的，否则将激起民愤，甚至引发暴动。恺撒深知这一点，因此，他的新建筑在选址时要避开这些神庙。

假设新的建筑物有P种规格，每种建筑物都是正方形的，占地为Ti Ti格 (1<=i<=P)。恺撒想知道对于每种规格的建筑，有多少种不同的合适选址方案（一种合适的选址方案指的是在该建筑所占的正方形区域内不存在神庙）。作为他的内务部长，这个光荣而艰巨的任务自然交给你来完成。

【输入】

　　输入文件第一行包含三个数，分别代表N,M,P (1<=N,M<=100,1<=P<=100)。随后的n行，每行有m个0或1（1表示该格为废墟，0表示该格有神庙）。接下来的P行每行有一个整数 (1< <=max(M,N))，代表的第i种建筑物的边长。

【输出】

输出文件有P行，每行一个整数，第行的数代表边长为的建筑物选址方案数。

【样例输入】

4 4 2
1011
1111
1110
1110
2
3

【样例输出】

5
1

C题　车站

【问题描述】

　　辖区内新开了一条高速公路，公路上有两个车站，坐标分别为A（xa，ya）、B（xb，yb），每天都有车辆从A站开往B站。公路附近有两个村庄（公路可能从村庄中穿过），村庄分布在如图所示的带状区域内，坐标为C（xc，yc），D（xd，yd），C、D两村每天都分别有m人要前往B站。

因为高速公路不可随意出入，所以需要在两车站之间的公路上合理地设置一些汽车停靠点，村民可步行至停靠点后进入高速公路，并免费乘车前往B站。每个村民每步行一千米（一个单位看作一千米）所得到的政府补贴为t元，政府维护一个停靠点所需花费为p元/年。应如何设置这些停靠点，才能使政府的支出最小？
　　给出一个年份year，请你设计一个方案，使得镇政府从该年起的n年内总支出最小，注意考虑闰年情况。
　　注意，村民只能进入停靠点而不能直接进入车站，但允许在车站处设置停靠点。

【输入】
　　　　第一行四个数： xa ya xb yb
　　　　第二行四个数： xc yc xd yd
　　　　第三行四个数： m n t p （0<=3000，0<=10）

第四行一个数： year （2000<year<3000）
以上数字，m，year，n为正整数，p，t为正实数，其余均为实数。

【输出】

　　第一行最小费用c（单位：元）
　　　　第二行设置的停靠点数N（N为正整数）
　　　　以下N行，每行两个实数，代表停靠点的坐标
　　　　如有多解，任意输出一解即可。
　　　　所有实数保留四位小数。

【样例输入】

-5 0 5 0

-1 -1 1 1

1 1 1 500

2001

【样例输出】

1532.3759

0.0000 0.0000

求一些经典算法题，要求有题目要求，最好有解题思路(思路说的详细一些)和原码。
比如：
要求：做一个带括号的整数的四则混合算法。
思路：用堆栈实现。（我说的不详细，说详细的说不出来，太菜）
代码：下一页
---------------------------------------------------------------

主要确立括号优先运算的问题
输入 a*((b+c)*(d+e)) 确定三个括号的优先运算
定义优先及高则递增
主要在于解析给内嵌更高的运算级别
出现一个括号记录括号数目及优先及如上面的括号数 1 优先及为1 括号数2，3 优先及2
定义括号计算结果变量解吸完毕后再根据优先及运算的出最终结果

这是俺以前写的，用的是c＋＋
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

double GetVal(string s)
{
           do
           {
                       string::size_type idxM = s.find_first_of("*/");
                       if (idxM != s.npos)
                       {
                                   string::size_type idxL;
                                   string::size_type idxR;

                                   if (idxM != 0 && idxM != s.size() - 1)
                                   {
                                               idxL = s.find_last_of("+-/*", idxM - 1);
                                               idxR = s.find_first_of("+-/*", idxM + 1);
                                   }
                                   else if (idxM == 0)
                                   {
                                               idxL = s.npos;
                                   }
                                   else
                                   {
                                               idxR = s.npos;
                                   }

                                   string::size_type L;
                                   string::size_type R;

                                   if (idxL == s.npos)            {L = 0;}
                                   else                                                {L = idxL + 1;}
                                   if (idxR == s.npos) {R = s.size();}
                                   else                                                {R = idxR;}

                                   double d1 = atof(string(s, L, idxM - L).c_str());
                                   double d2 = atof(string(s, idxM + 1, R - idxM - 1).c_str());

                                   double d3;
                                   switch(s.at(idxM))
                                   {
                                   case '*':
                                               d3 = d1 * d2;
                                               break;
                                   case '/':
                                               d3 = d1 / d2;
                                               break;
                                   default:
                                               cout << "error";
                                   }

                                   char buffer[25];
                                   s.replace(L, R - L, _gcvt(d3, 12, buffer));
                                   GetVal(s);
                       }
                       else if ((idxM = s.find_first_of("+-")) != s.npos)
                       {
                                   string::size_type idxL;
                                   string::size_type idxR;

                                   if (idxM != 0 && idxM != s.size() - 1)
                                   {
                                               idxL = s.find_last_of("+-", idxM - 1);
                                               idxR = s.find_first_of("+-", idxM + 1);
                                   }
                                   else if (idxM == 0)
                                   {
                                               idxL = s.npos;
                                   }
                                   else
                                   {
                                               idxR = s.npos;
                                   }

                                   string::size_type L;
                                   string::size_type R;

                                   if (idxL == s.npos)            {L = 0;}
                                   else                                                {L = idxL + 1;}
                                   if (idxR == s.npos) {R = s.size();}
                                   else                                                {R = idxR;}

                                   double d1 = atof(string(s, L, idxM - L).c_str());
                                   double d2 = atof(string(s, idxM + 1, R - idxM - 1).c_str());

                                   double d3;
                                   switch(s.at(idxM))
                                   {
                                   case '+':
                                               d3 = d1 + d2;
                                               break;
                                   case '-':
                                               d3 = d1 - d2;
                                               break;
                                   default:
                                               cout << "error";
                                   }

                                   char buffer[25];
                                   s.replace(L, R - L, _gcvt(d3, 12, buffer));
                       }
                       else
                       {
                                   break;
                       }
           } while(1);
           return atof(s.c_str());
}

double DealWithBracketExpr(string str)
{
           do
           {
                       string::size_type idxR = str.find_first_of(')');
                       if (idxR == str.npos){break;}
                       string::size_type idxL = str.find_last_of('(', idxR);

                       string strTemp(str, idxL, idxR - idxL + 1);
                       strTemp.erase(remove(strTemp.begin(), strTemp.end(),
                                   '('),
                                   strTemp.end());
                       strTemp.erase(remove(strTemp.begin(), strTemp.end(),
                                   ')'),
                                   strTemp.end());

                       double d = GetVal(strTemp);
                       char buffer[25];
                       str.replace(idxL, idxR - idxL + 1, _gcvt(d, 12, buffer));
           } while(1);

           return atof(str.c_str());
}

int main()
{
           //string str("(1.23+23)*45+34/34-56.9");
           cout << "Enter your expression:" << endl;
           string str;
           cin >> str;

           str.insert(str.begin(), '(');
           str.insert(str.end(), ')');

cout << DealWithBracketExpr(str) << endl;

           return 0;
}
---------------------------------------------------------------

算术表达式存放在expression.dat中。每个算术表达式用“；”号结束。如：
-1+3+5/5*2;
5+(-36);
1+(-8-3);
1+8/2;
6-5;
(-1+2)*3+(8-7)-1*(2+5);
(1+6*8+9-2)*2+8-4;
6/(3-3);
((1-2)/3+4;

该程序具有四则运算功能，并且能够判别简单的错误。如：括号不匹配、多余运算符、除数不能等于0等。

代码：
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
“oper.h”

struct StackNode;
typedef struct StackNode *PtrToNode;
typedef PtrToNode Stack;

Stack CreatStack(void);
void Push(int x,Stack S);
int Top(Stack S);
int IsEmpty(Stack S);
void Pop(Stack S);
void Scaner(void);
void getch(void);
void getbc(void);
void retract(void);
int digit(char ch);
void concat(void);
void Operate(void);
void MakeEmpty(Stack S);
void CheckErr(void);
---------------------------------------------------------------

代码：
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
"main.c"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "oper.h"

FILE *fp;
Stack NumStack,OpStack;
char ch;
char token[20];
int flag=2; /*当flag=2时,表示输入的'-'号当作负号*/

struct StackNode
{ int Element;
PtrToNode next;
};

int main(int argc, char *argv[])
{
if((fp=fopen("expression.dat","r"))==NULL)
           {
                       printf("Can't open this file/n");
            system("pause");
                       exit(0);
           }
           NumStack=CreatStack();
           OpStack=CreatStack();
           while(!feof(fp))
                       Scaner();
           fclose(fp);
system("PAUSE");
return 0;
}

Stack CreatStack(void)
{
Stack S;
S=(Stack)malloc(sizeof(struct StackNode));
if(S==NULL)
{printf("Out of space !!");exit(1);}
S->next=NULL;
           return S;
}

void Push(int x,Stack S)
{
PtrToNode TmpCell;
TmpCell=(PtrToNode)malloc(sizeof(struct StackNode));
if (TmpCell==NULL)
{printf("Out of space !!");exit(1);}
else
{
TmpCell->Element=x;
TmpCell->next=S->next;
S->next=TmpCell;
}
}

int Top(Stack S)
{
if(IsEmpty(S))
{
                       printf("表达式有错!! ");
                       CheckErr();
                       exit(1);
           }
else
return S->next->Element;
}

int IsEmpty(Stack S)
{
return S->next==NULL;
}

void Pop(Stack S)
{
PtrToNode FirstCell;
if(IsEmpty(S))
{printf("The stack is empty !!/n");exit(1);}
else
{
FirstCell=S->next;
S->next=S->next->next;
free(FirstCell);
}
}

void MakeEmpty(Stack S)
{
           if(!IsEmpty(S))
                       S->next=NULL;
}

void getch() /*从缓冲区读入一字符*/
{
           ch=fgetc(fp);
}

void getbc() /*若ch中是空白字符，则不停调用getch()直到读入的不是空白字符为止*/
{
           while (ch==' ')
                       getch();
}

void retract() /*指针回退一个字符*/
{
           fseek(fp,ftell(fp)-1L,0);
}

int digit(char ch) /*判断ch中的是否是数字*/
{
           return isdigit((int)ch);
}

void concat() /*将ch中的字符连接到token的后面*/
{
           unsigned int i;
           i=strlen(token);
           token[i]=ch;
           token[i+1]='/0';
}

void Operate(void)
{
           int a,b;
           a=Top(NumStack);
           Pop(NumStack);
           b=Top(NumStack);
           Pop(NumStack);
           switch(Top(OpStack))
           {
                       case'*':Push(b*a,NumStack);break;
                       case'/':if(a==0) {printf("除数不能为零!!");system("pause");exit(1);}
                                    Push(b/a,NumStack);break;
            case'-':Push(b-a,NumStack);break;
                       case'+':Push(b+a,NumStack);break;
default:printf("the operation is error ! /n");
           }
           Pop(OpStack);
}

void CheckErr()
{
           if (!IsEmpty(OpStack))
           {
                       if(Top(OpStack)=='(') printf("括号不匹配!/n");
                       else printf("有多余运算符!/n");
           }
           else
                       printf("未知错误!/n");
}