Meta-Loopless Sorts

Background

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

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

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

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

Sample Input

1
3

Sample Output

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.

 

Ideas : Simulate insert sort , Insert one element at a time , Compare back to front when inserting elements .

#include<cstdio>
#include<string>
using namespace std;
int n;
string str;
static const char *indent[] = { "",
" ", " ", " ", " ", " ", " ",
" ", " ", " " };
char alphas[]="abcdefgh"; void dfs(int cur)
{
if(cur==n)
{
printf("%s", indent[cur]);
printf("writeln(%c", str[0]);
for (int i = 1; i < n; i++)
printf(",%c", str[i]);
printf(")\n");
return;
}
// From the tail to the front
for(int i=str.size()-1; i>=0; i--)
{
printf("%s", indent[cur]);
if(i!=(int)str.size()-1)
printf("else ");
printf("if %c < %c then\n", str[i], alphas[cur]);
str.insert(i+1, 1, alphas[cur]);
dfs(cur+1);
str.erase(i+1, 1);
}
// Insert to the front
printf("%s", indent[cur]);
printf("else\n");
str.insert(0, 1, alphas[cur]);
dfs(cur+1);
str.erase(0, 1);
} int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
printf("program sort(input,output);\nvar\na");
for(int i=1;i<n;i++)
printf(",%c", 'a'+i);
printf(" : integer;\n");
printf("begin\n");
printf(" readln(a");
for (int i = 1; i < n; i++)
printf(",%c", 'a' + i);
puts(");");
str="a";
dfs(1);
puts("end."); if(T)
printf("\n");
}
return 0;
}

Uva110 Meta-Loopless Sorts More articles about

  1. Commonly used meta Arrangement

    <!--  Optimized for handheld devices , Mainly for some old unrecognized viewport Browser , Blackberry, for example  --> <meta name="HandheldFriendly" con ...

  2. meta label

    Reference resources :http://www.jb51.net/web/158860.html META The label is divided into two parts :HTTP Heading information (HTTP-EQUIV) And page description information (NAME). One .HTTP Heading information (HTT ...

  3. Django Model class Meta Metadata details

    from :https://my.oschina.net/liuyuantao/blog/751337 brief introduction Use internal class Meta  Define the metadata of the model , for example : from django.db impo ...

  4. H5 meta Summary

    <meta name="viewport" content="width=device-width,initial-scale=1,minimum-scale=1, ...

  5. Asp.net Add... In the background CSS、JS、Meta label

    Asp.net Add... In the background CSS.JS.Meta How to write a label , I write a function here for future use . If the function is in the page class , Page Parameters can also be omitted . First, import the namespace using System.Web.UI.Htm ...

  6. More complete meta

    <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  7. Browser kernel control Meta Label description document 【 turn 】

    Background introduction Because of the well-known situation , Domestic mainstream browsers are dual core browsers : be based on Webkit The kernel is used for high-speed browsing of common websites . be based on IE The kernel is compatible with online banking . Old website . With 360 For example, a few browsers of , We have priority in passing Webkit Kernel configuration ...

  8. HTML &lt;meta&gt; label , Search engine

    About Mate A detailed explanation of the label , Please check out w3school The website is :http://www.w3school.com.cn/tags/tag_meta.asp meta Function of label META The label is HTML Mark HEA ...

  9. Kernel control Meta label : Give Way 360 By default, the browser uses the speed mode to open the web page ( turn )

    In order to make the web page less bloated , Also lazy reason IE 了 , At the same time, more domestic dual core browsers , Add the following two lines to the page header Meta Control tags . 1, Add... To the page header <meta name="renderer&quo ...

Random recommendation

  1. Oracle 11g The detailed steps of database installation are illustrated

    1. Come first Oracle Download on the official website 11g oracle Database 11g  The first 2 edition (11.2.0.1.0) The standard version . The standard version 1 And enterprise Apply to Microsoft Windows (x64 ...

  2. FL2440 Drive add (4)LED Drive add

    Hardware information :FL2440 The board ,s3c2440CPU Take four LED, Respectively in the link GPB5,GPB6,GPB8,GPB10 Kernel version :linux-3.8.0 led The driver code is as follows : It's worth noting that : 1, Timer ...

  3. [tools]QuickPing

    An artifact quickping It can quickly detect which addresses the network is disconnected from .   The online one will show green online + Those with a host name are shown in bright green

  4. BZOJ3713: [PA2014]Iloczyn

    3713: [PA2014]Iloczyn Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 206  Solved: 112[Submit][Status ...

  5. Wencheng little pot friend python-num2 data type 、 list 、 Dictionaries

    One . Let's talk about it first python Operation process Computers are unable to recognize high-level languages , So when we run a high-level language program , You just need one “ Translation machine ” To engage in the process of converting high-level languages into machine languages that computers can read . This process falls into two categories , The first is ...

  6. Java Strong citation , Soft citation , Weak reference

    1. Strong citation public void handleMessage(Message msg) { case FAIL: GoplayException mException = new GoplayExc ...

  7. Recommended to use domestic Douban source installation Python plug-in unit

    Used to pip install Python The plug-in , Until today, pip In fact, the principle is from Python The official source of pypi.python.org/pypi Download to local , Then unpack and install But sometimes , It's going to be very slow , At home, we can go through ...

  8. Move app The experiential test of

    Recently, user experience has been mentioned a lot , You may come across this situation , Customer “ Your software functions are OK , But it just doesn't feel good , Can we optimize , Make it bigger ”, As an experienced test engineer, you should know that the problem is user experience About ...

  9. When your layui You have to select all the forms + Delete function 【 compatible ie8】

    <!-- Future generations --> <div class="choose"> <input type="checkbox" id=" ...

  10. 2018 year 4 Mid month PTA( 3、 ... and )

    C Senior third time PTA Homework (1) subject 6-1 Output the English name of the month 1. Design thinking (1) Algorithm ( Subfunctions ) First step : Define the name of character type first level pointer sub function getmonth, Parametric integers n. The second step : Define the length as 12 Character array pointer to mo ...