UVA110 题目要求输入一个整数，然后输出一个pascal的可运行的程序，但程序中只能宥比较，if，else，if else等的语句，在程序中使用了递归算法，写好后觉得这个类似与一个生成1.。。。n的所有数的排列数
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAX 9
#define STEP 2
struct meta {
int num;
int var[MAX];
} Meta;
void space(int n)
{
for (int i = 0; i < n; i++) printf(" ");
}
void out(const struct meta &Meta)
{
for (int i = 0; i < Meta.num - 1; i++) printf("%c,", 'a' + Meta.var[i]);
printf("%c", Meta.var[Meta.num - 1] + 'a');
}
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
// insert after the index element....
void move(const struct meta &in, struct meta &o, int index, int len)
{
int i, t;
o = in;
t = in.var[len - 1];
for (i = len - 1; i > index; i--)
o.var[i] = o.var[i - 1];
o.var[i] = t;
}
void meta_loop(struct meta Meta, const int index, const int indent)
{
struct meta tmp;
int i;
i = index - 1;
space(indent); printf("if %c < %c then\n",
Meta.var[i] + 'a', Meta.var[index] + 'a');
if (Meta.num - index == 1) {
space(indent + STEP); printf("writeln("); out(Meta); printf(")\n");
} else
meta_loop(Meta, index + 1, indent + STEP);
for (i--; i >= 0; i--) {
space(indent); printf("else if %c < %c then\n",
Meta.var[i] + 'a', Meta.var[index] + 'a');
move(Meta, tmp, i + 1, index + 1);
if (tmp.num - index == 1) {
space(indent + STEP); printf("writeln("); out(tmp); printf(")\n");
} else
meta_loop(tmp, index + 1, indent + STEP);
}
move(Meta, tmp, 0, index + 1);
space(indent); printf("else\n");
if (tmp.num - index == 1) {
space(indent + STEP); printf("writeln("); out(tmp); printf(")\n");
} else
meta_loop(tmp, index + 1, indent + STEP);
}
int main(void)
{
int i, j, n;
char buf[32];
gets(buf); sscanf(buf, "%d", &n);
gets(buf); // just ignore the empty line.
for (i = 0; i < n; i++) {
gets(buf); sscanf(buf, "%d", &Meta.num);
if (i != n - 1) gets(buf); // there will be a blank line between test cases.
for (j = 0; j < Meta.num; j++) Meta.var[j] = j;
printf("program sort(input,output);\nvar\n");
out(Meta);printf(" : integer;\nbegin\n");
space(2); printf("readln(");out(Meta);printf(");\n");
if (Meta.num == 1) {
space(2); printf("writeln(a)\n");
} else
meta_loop(Meta, 1, 2);
printf("end.\n");
if (i != n - 1) printf("\n");
}
return 0;
}
UVA112 这道题目相对前一道题目比较简单，因为毕业设计的做的是编译原理方面的。这倒题目类似建立一个语法树，然后对这个语法树进行遍历，计算出根节点到叶节点的路径。。。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
static int total;
static int flag;
struct tree {
int n;
struct tree *pleft, *pright;
};
void skipspace()
{
char ch;
while (1) {
ch = getchar();
if (ch == ' ' || ch == '\n' || ch == '\t') continue;
else break;
}
ungetc(ch, stdin);
}
int GetInt()
{
int n, mark = 1;
char ch;
skipspace();
n = 0;
if ((ch = getchar()) == '-')
mark = -1;
else n = ch - '0';
while (isdigit(ch = getchar())) {
n = n*10 + ch - '0';
}
ungetc(ch, stdin);
return n*mark;
}
char GetChar(void)
{
skipspace();
return getchar();
}
void match(const char c)
{
char ch = GetChar();
if (ch != c) {
//assert(0);
//printf("yeah...... invalid tree\n");
flag = 1;
}
}
struct tree * build_tree()
{
struct tree *root = NULL;
match('(');
char ch = GetChar(); ungetc(ch, stdin);
if (isdigit(ch) || ch == '-') {
root = new struct tree;
root->n = GetInt();
root->pleft = build_tree();
root->pright = build_tree();
}
match(')');
return root;
}
int search_tree(struct tree *root, int value)
{
if (!root) return 0;
if (root->pleft == NULL && root->pright == NULL) {
value += root->n;
return value == total;
}
if (root->pleft && search_tree(root->pleft, value + root->n)) return 1;
return root->pright ? search_tree(root->pright, value + root->n) : 0;
}
void print_tree(struct tree *root, int indent)
{
if (!root) return;
for (int i = 0; i < indent; i++) printf(" ");
printf("%d\n", root->n);
print_tree(root->pleft, indent + 2);
print_tree(root->pright, indent + 2);
}
void destroy_tree(struct tree *root)
{
if (root) {
destroy_tree(root->pleft);
destroy_tree(root->pright);
delete root;
}
}
int main(void)
{
struct tree *root;
int ch;
while ((ch = GetChar()) != EOF) {
ungetc(ch, stdin);
flag = 0;
total = GetInt();
root = build_tree();
if (flag == 1 || !search_tree(root, 0)) printf("no\n");
else printf("yes\n");
//print_tree(root, 0);
destroy_tree(root);
}
return 0;
}