posts - 2,  comments - 8,  trackbacks - 0

题目要求基本如下:
请编写一个控制台程序,要求用户可以输入任意组条件,定义两个字母之间的大小关系。程序可以通过已输入的条件,推断出给定的两个字母之间的大小关系。例如:
用户输入:A>B
用户输入:B>C
用户输入:A?C
程序显示:A>C
用户输入:C<D
用户输入:A?D
程序显示:无法判断
用户输入:A<C
程序显示:与原有条件冲突
。。。
字母仅为 26 个英文字母之一,条件只有大于和小于两种,问号表示向计算机提问。程序要能检查用户输入的语法是否正确,检查条件是否于原有的条件冲突,并输入判断结果。

其实这个题目考的是如何选择一个好的数据结构,来实现这个算法。


我的思路就是使用最简单的二维数组来表达,具体如下:
总共只有 26 个英文字母,所以不访定义一个26X26的二维字符数组来保存相互之间的关系;
因为关系是相互的,所以只需要矩阵的上半部分或者下半部分(不过26X26也不算很大,就算了吧~~);

例如:    如果用户输入了A>B,先查询AB之间的大小关系,如果与‘>’冲突,则提示出错;

不存在冲突则设置[A][B]='>'[B][A]='<';并且做如下设置:将所以小于B的字符都小于A、所有大于A的字符都大于B

如果用户查询两个字符之间的关系,则直接从二维表中查找二者的关系并输出

这样一来,问题就迎刃而解了

具体代码如下:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define UNKNOWN  'u'
#define LARGER   '>'
#define LESS    '<'

#define MAX_COL    26

//
初始化二维数组
void Init();

//
打印二维数组
void Print();

//
查询两个字符的大小关系
bool Query(char v1,char v2);

//
输入两个字符的大小关系
bool Input(char v1,char op,char v2);

//
获取两个字符的大小关系
char GetRel(char v1,char v2);

//
设置两个字符的大小关系
void SetRel(char v1,char v2,char op);


char matrix[MAX_COL][MAX_COL];

//
主函数
int main()
{
    Init();

    char buf[8];
    char v1,op,v2;

    while(true)
    {
        printf("
用户输入:");
        memset(buf,0,8);
        scanf("%s",buf);

        strupr(buf);

        if(strcmp(buf,"EXIT")==0
            ||strcmp(buf,"QUIT")==0
            ||strcmp(buf,"Q")==0
            )
            break;
        if(strcmp(buf,"PRINT")==0
            ||strcmp(buf,"P")==0 )
        {
            Print();
            continue;
        }

        v1=buf[0];
        op=buf[1];
        v2=buf[2];

        if(!isalpha(v1) || !isalpha(v2))
        {
            printf("Error:Invalid char!\n");
            continue;
        }

        if(op=='?')
        {
            Query(v1,v2);
        }
        else if(op == '>' || op == '<')
        {
            if(v1==v2)
            {
                printf("Error:two chars are equal!\n");
                continue;
            }
            Input(v1,op,v2);
        }
        else
        {
            printf("Error:Unknown operator!\n");
        }
    }
}



void Init()
{
    for(int i=0;i<MAX_COL;i++)
    {
        for(int j=0;j<MAX_COL;j++)
        {
            matrix[i][j]=UNKNOWN;
        }
    }
}

void Print()
{
    for(int i=0;i<MAX_COL;i++)
    {
        for(int j=0;j<MAX_COL;j++)
        {
            printf("%c",matrix[i][j]);
        }
        printf("\n");
    }
}

bool Query(char v1,char v2)
{
    char rel=GetRel(v1,v2);
    switch(rel)
    {
    case UNKNOWN:
        printf("
程序显示:无法判断\n");       
        return true;
    }
    printf("
程序显示:%c%c%c\n",v1,rel,v2);
    return true;
}

bool Input(char v1,char op,char v2)
{
    char rel=GetRel(v1,v2);
    if(rel==UNKNOWN)
    {
        SetRel(v1,v2,op);

        //
v1>v2,则所有比v1大的符号都将比v2,所有比v2小的符号都将比v1
        if(op == LARGER)
        {
            for(int i='A';i<='Z';i++)
            {
                if(LARGER ==GetRel(i,v1))
                {
                    SetRel(i,v2,LARGER);
                }
                if(LESS == GetRel(i,v2))
                {
                    SetRel(i,v1,LESS);
                }
            }
        }
        //
v1<v2,则所以小于v1的符号都比v2小,所有大于v2的符号都将比v1
        else if(op==LESS)
        {
            for(int i='A';i<='Z';i++)
            {
                if(LESS ==GetRel(i,v1))
                {
                    SetRel(i,v2,LESS);
                }
                if(LARGER == GetRel(i,v2))
                {
                    SetRel(i,v1,LARGER);
                }
            }
        }
    }
    else if(rel != op)
    {
        printf("
程序显示:与原有条件冲突\n");
        return false;
    }
    return true;
}

char GetRel(char v1,char v2)
{
    return matrix[v1-'A'][v2-'A'];
}

void SetRel(char v1,char v2,char op)
{
    matrix[v1-'A'][v2-'A']=op;
    matrix[v2-'A'][v1-'A']=(op==LARGER)?LESS:LARGER;
}

posted on 2007-06-29 17:32 Darkblue 阅读(1482) 评论(4)  编辑 收藏 引用

FeedBack:
# re: 一道微软的Mini-Test笔试题(二)
2007-06-29 17:56 | SuperPlayeR
这个题目我有个思路,不过现在下班了,思路还没成熟。嘿嘿~~~晚点再奉上  回复  更多评论
  
# re: 一道微软的Mini-Test笔试题(二)
2007-06-30 00:58 | flyman
# re: 一道微软的Mini-Test笔试题(二)
2007-07-03 16:16 | Darkblue
@SuperPlayeR

巴着眼等着你的思路呢,嘿嘿~~
  回复  更多评论
  
# re: 一道微软的Mini-Test笔试题(二)
2007-07-03 16:17 | Darkblue
@flyman
不错不错,用面向对象的方式实现的!
测试了几个,好像没什么问题  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔档案

最新评论

阅读排行榜

评论排行榜