Bermudez C 第 5 章 P 2：升序时不使用数组或循环

Question

正在阅读 Bermudez 的 C Programming Tutorial（KN King 的书的补充），并对第 5 章（选择语句）的第二个问题感到困惑。

题目如下：写一个程序，读入五个值，并按升序写出。

初出茅庐的程序员不允许使用数组或循环。唯一可用的工具是 "if" 和 "switch" 语句。

这是我的问题：我用蛮力解决了这个问题——这太不优雅了。一种猜测是我应该对这个练习感到不安；也就是说，也许 Bermudez 想展示一个人需要做 5 次的 reader！完全依赖 "if" and/or "switch" 语句时的排列。

另一种猜测（可能是更有可能的猜测）是我做错了什么。有些东西告诉我，我至少可以将这段代码减半。

有什么建议吗？

Answer 1

我有一个算法，但它用递归作弊。

它使用 O(n) 堆栈，O(n^2) 时间复杂度。

#include <stdio.h>
#include <stdbool.h>

bool sorted;

void sort(int a, int b, int c, int d, int e) {
    if (sorted) return;
    if (a <= b && b <= c && c <= d && d <= e) {
        printf("%d %d %d %d %d\n", a, b, c, d, e);
        sorted = true;
    } else {
        if (a > b) sort(b, a, c, d, e);
        if (b > c) sort(a, c, b, d, e);
        if (c > d) sort(a, b, d, c, e);
        if (d > e) sort(a, b, c, e, d);
    }
}

int main() {
    sorted = false;
    sort(5, 4, 2, 3, 1);
    return 0;
}

关于BF算法，也许一次比较2个数字可能会导致一些简单。许多算法导致树遍历，效率有很多因素，如剪枝，分支选择等

UPD

因此，对于这个问题，总共有 5!=120 种情况。所以 120 if else 可以解决它...

if (a <= b && b <= c && c <= d && d <= e)...
else (b <= a && b <= c && c <= d && d <= e)...

Answer 2

这可能真的是作弊，但可以通过 Sorting Network.

中的一小段代码来完成

#include <stdio.h>

int main()
{
    int a, b, c, d, e, temp;

    printf("Program 5.2: Ascending Order of Values\n");
    printf("======================================\n\n");

    printf("Enter first value: ");
    scanf("%d", &a);

    printf("Enter second value: ");
    scanf("%d", &b);

    printf("Enter third value: ");
    scanf("%d", &c);

    printf("Enter fourth value: ");
    scanf("%d", &d);

    printf("Enter fifth value: ");
    scanf("%d", &e);

    printf("\nRe-arranged in ascending order: \n");
    printf("===============================\n\n");

    /* Sorting Network - 9 comparators */
    if (a > b) { temp = a; a = b; b = temp; } // 0,1
    if (d > e) { temp = d; d = e; e = temp; } // 3,4
    if (c > e) { temp = c; c = e; e = temp; } // 2,4
    if (c > d) { temp = c; c = d; d = temp; } // 2,3
    if (a > d) { temp = a; a = d; d = temp; } // 0,3
    if (a > c) { temp = a; a = c; c = temp; } // 0,2
    if (b > e) { temp = b; b = e; e = temp; } // 1,4
    if (b > d) { temp = b; b = d; d = temp; } // 1,3
    if (b > c) { temp = b; b = c; c = temp; } // 1,2

    printf("%d %d %d %d %d\n", a, b, c, d, e);

    return 0;
}

Demo on ideone.com

Answer 3

我的解决方案不像@Blastfurnace 的那样优雅，但我认为您应该将每个元素与其他元素进行比较，并使用该比较确定它的最终位置（有点像快速排序）。它仍然是相当多的代码，但我认为它更容易理解和更简单...

时间复杂度： n*(n-1) [count] + n^2 [switch] == 2*(n^2) - n < n! [对于大数字（例如 5 :) ）] space 复杂度： n [初始变量] + n[count] + n[first,second...] = 3n

int main()
{
    int a,b,c,d,e;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    scanf("%d",&d);
    scanf("%d",&e);

    int a_count = 0;
    int b_count = 0;
    int c_count = 0;
    int d_count = 0;
    int e_count = 0;
    int first,second,third,fourth,fifth;

    if(a>b)
        ++a_count;
    if(a>c)
        ++a_count;
    if(a>d)
        ++a_count;
    if(a>e)
        ++a_count;

    if(b>a)
        ++b_count;
    if(b>c)
        ++b_count;
    if(b>d)
        ++b_count;
    if(b>e)
        ++b_count;

    if(c>a)
        ++c_count;
    if(c>b)
        ++c_count;
    if(c>d)
        ++c_count;
    if(c>e)
        ++c_count;

    if (d>a)
        ++d_count;
    if (d>b)
        ++d_count;
    if (d>c)
        ++d_count;
    if (d>e)
        ++d_count;

    if (e>a)
        ++e_count;
    if (e>b)
        ++e_count;
    if (e>c)
        ++e_count;
    if (e>d)
        ++e_count;
    switch(a_count){
        case 0:
            first = a;
            break;
        case 1:
            second = a;
            break;  
        case 2:
            third = a;
            break;
        case 3:
            fourth = a;
            break;
        case 4:
            fifth = a;
            break;              
    }

    switch(b_count){
        case 0:
            first = b;
            break;
        case 1:
            second = b;
            break;  
        case 2:
            third = b;
            break;
        case 3:
            fourth = b;
            break;
        case 4:
            fifth = b;
            break;              
    }   

    switch(c_count){
        case 0:
            first = c;
            break;
        case 1:
            second = c;
            break;  
        case 2:
            third = c;
            break;
        case 3:
            fourth = c;
            break;
        case 4:
            fifth = c;
            break;              
    }

    switch(d_count){
        case 0:
            first = d;
            break;
        case 1:
            second = d;
            break;  
        case 2:
            third = d;
            break;
        case 3:
            fourth = d;
            break;
        case 4:
            fifth = d;
            break;              
    }       

    switch(e_count){
        case 0:
            first = e;
            break;
        case 1:
            second = e;
            break;  
        case 2:
            third = e;
            break;
        case 3:
            fourth = e;
            break;
        case 4:
            fifth = e;
            break;              
    }   

    printf("%d %d %d %d %d\n", first,second,third,fourth,fifth);
    return 0;
}

最后一件事：这里的每个解决方案都不会像使用简单循环那样简单优雅。我确实认为 Bermudez 打算展示如何解决该语言的这些基本功能，但要让您记住这种解决方法非常不舒服:)

Bermudez C 第 5 章 P 2：升序时不使用数组或循环

Bermudez C Chapter 5 P 2: No use of arrays or loops for ascending order

c

conditional