首页 > 搜索 > 回溯和剪枝 > hdu 1617 Meta-Loopless Sorts-模拟-[解题报告]
2013
12-16

hdu 1617 Meta-Loopless Sorts-模拟-[解题报告]

Meta-Loopless Sorts

问题描述 :

Sorting holds an important place in computer science. Analyzing and implementing various sorting algorithms forms an important part of the education of most computer scientists, and sorting accounts for a significant percentage of the world’s computational resources. Sorting algorithms range from the bewilderingly popular Bubble sort, to Quicksort, to parallel sorting algorithms and sorting networks. In this problem you will be writing a program that creates a sorting program (a meta-sorter).

The problem is to create several programs whose output is a standard Pascal program that sorts n numbers where n is the only input to the program you will write. The Pascal programs generated by your program must have the following properties:

They must begin with program sort(input,output);

They must declare storage for exactly n integer variables. The names of the variables must come from the first n letters of the alphabet (a,b,c,d,e,f).

A single readln statement must read in values for all the integer variables.

Other than writeln statements, the only statements in the program are if then else statements. The boolean conditional for each if statement must consist of one strict inequality (either < or >) of two integer variables.

Exactly n! writeln statements must appear in the program.

Exactly three semi-colons must appear in the programs

1.after the program header: program sort(input,output);

2.after the variable declaration: …: integer;

3.after the readln statement: readln(…);

No redundant comparisons of integer variables should be made. For example, during program execution, once it is determined that a < b, variables a and b should not be compared again.

Every writeln statement must appear on a line by itself.

The programs must compile. Executing the program with input consisting of any arrangement of any n distinct integer values should result in the input values being printed in sorted order.
For those unfamiliar with Pascal syntax, the example at the end of this problem completely defines the small subset of Pascal needed.

输入:

The input consist on a number in the first line indicating the number M of programs to make, followed by a blank line. Then there are M test cases, each one consisting on a single integer n on a line by itself with 1 ≤ n ≤8. There will be a blank line between test cases.

输出:

The output is M compilable standard Pascal programs meeting the criteria specified above. Print a blank line between two consecutive programs.

样例输入:

1

3

样例输出:

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if b < c then
      writeln(a,b,c)
    else if a < c then
      writeln(a,c,b)
    else
      writeln(c,a,b)
  else
    if a < c then
      writeln(b,a,c)
    else if b < c then
      writeln(b,c,a)
    else
      writeln(c,b,a)
end.

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

int t, n, i;
int cc[10];
void swap(int &a, int &b)
{
	int t = a;
	a = b;
	b = t;
}
void insert(int num, int *cc) {
	int i;
	if (num == n)
	{
		int nu = num * 2;
		while (nu --) {printf(" "); }
		printf("writeln(");
		for (i = 0; i < n - 1; i++) {
			printf("%c,", cc[i] + 'a');
		}
		printf("%c)\n", cc[n - 1] + 'a');
			return;
	}
	int c[10];
	for (i = 0; i < num; i ++)
		c[i] = cc[i];
	for (i = num; i >= 0; i --) {
		if (num == i) {
			int nu = num * 2;
			while (nu --) {printf(" "); }
			c[i] = i;
			printf("if %c < %c then\n", c[i - 1] + 'a', num + 'a');
			insert(num + 1, c);
		}
		else if (i == 0) {
			int nu = num * 2;
			while (nu --) {printf(" "); }
			printf("else\n");
			swap(c[i], c[i + 1]);
			insert(num + 1, c);
		}
		else {
			int nu = num * 2;
			while (nu --) {printf(" "); }
			printf("else if %c < %c then\n", c[i - 1] + 'a', num + 'a');
			swap(c[i], c[i + 1]);
			insert(num + 1, c);
		}
	}
}
void out() {
	printf("program sort(input,output);\n");
	printf("var\n");
	for (i = 0; i < n - 1; i++) {
		printf("%c,",'a' + i);
	}
	printf("%c : integer;\n", 'a' + n - 1);
	printf("begin\n");
	printf("  readln(");
	for (i = 0; i < n - 1; i++) {
		printf("%c,",'a' + i);
	}
	printf("%c);\n", 'a' + n - 1);
	insert(1, cc);
	printf("end.\n");
	if (t) printf("\n");
}

int main() {
	scanf("%d", &t);
	while (t --) {
		memset(cc, 0, sizeof(cc));
		scanf("%d", &n);
		out();
	}
	return 0;
}

解题转自:http://blog.csdn.net/accelerator_/article/details/9904739


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  4. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义