Блог

Главная - Вопросы по программированию - Можно ли сортировать целые числа с помощью этого очень ограниченного набора операторов?

Можно ли сортировать целые числа с помощью этого очень ограниченного набора операторов?

#arrays #algorithm #sorting #integer

Вопрос:

Фон

Я работаю на странном языке программирования с очень ограниченным набором инструментов.

Я хочу отсортировать список целых чисел, но я не могу найти алгоритм, который работает с учетом инструментов. Я даже не знаю, возможно ли это вообще.

Операторы

Это некоторый код JavaScript, который документирует доступные операторы.

 // 1. you can create new variables
// javascript quirk: in order to pass-by-reference, you must store an integer in an object
const v = (value) => {
    return { value: value };
}

// 2. you can set A to B, if B is larger than A
const max = (a,b) => {
    if(b.value > a.value)
        a.value = b.value;
};

// 3. you can set A to B, if B is less than A
const min = (a,b) => {
    if(b.value < a.value)
        a.value = b.value;        
};

// 4. you can swap the values of A and B
const swap = (a,b) => {
    let t = a.value;
    a.value = b.value;
    b.value = t;
};

// 5. you can set A to B
const set = (a,b) => {
    a.value = b.value;
};

// 6. you can add B to A
const add = (a,b) => {
    a.value = a.value   b.value;
};

// 7. you can subtract B from A
const subtract = (a,b) => {
    a.value = a.value - b.value;
};

// 8. you can multiply A by B
const multiply = (a,b) => {
    a.value = a.value * b.value;
};

// 9. you can divide A by B, losing the remainder
// if B == 0, then A is not modified
const divide = (a,b) => {
    if (b.value == 0) return;
    a.value = Math.floor(a.value/b.value);
};

// 10. you can set A to the remainder of A divided by B
// if B == 0, then A is not modified
const mod = (a,b) => {
    if (b.value == 0) return;
    a.value = a.value % b.value;
};

// 11. you can test if A falls within a range of integers, and if true, call a function 
// (see next section for function rules). You cannot do anything with a false
//
// min and max must be hard coded integers (i.e. you cannot pass in variables)
const in_range = (a,min,max) => {
    return (a >= min amp;amp; a <= max);
};

// 12. you can add an integer to A
// x must be a hard-coded integer, you cannot pass in variables
const add2 = (a,x) => {
    a.value = a.value   x;
};

// 13. you can set A to an integer
// x must be a hard-coded integer, you cannot pass in variables
const set2 = (a,x) => {
    a.value = x;
};

Ввод

     var a = v(2);
    var b = v(1);
    var c = v(3);

    // you may create as many extra variables as you want
    var temp = v(0);

Желаемый результат

     a.value == 1
    b.value == 2
    c.value == 3

Вопрос

Используя только перечисленные выше операции, можно ли отсортировать целые числа ?

Язык очень ограничен:

Нет никаких циклов или другого доступного потока сравнения/логики.

Массивов нет.

Вы можете писать функции, но они должны следовать приведенным выше правилам. Вы не можете передавать переменные функциям, к ним необходимо обращаться из глобальной области.

Комментарии:

1. Вам нужно отсортировать три переменные a , b , и c ? Не похоже, что в вашем языке есть массивы, верно?

2. Правильно, массивов нет.

Ответ №1:

Теперь, когда определения max и min были исправлены, вы можете сделать это так:

 var sum = v(0);
add(sum ,a);
add(sum ,b);
add(sum ,c);

//remember a and set a to min
var olda = v(0);
set(olda,a);
min(a,b);
min(a,c);

//set c to max
max(c,olda);
max(c,b);

//calculate b
set(b,sum);
subtract(b,a);
subtract(b,c);

У вас гораздо больше доступных операций, чем вам нужно. Очевидно, что проще, чем это, отсортировать только 2 переменные, и если вы можете отсортировать 2, то вы можете сортировать столько, сколько захотите, используя сеть сортировки.

Комментарии:

1. вы правы, я закодировал max и min неправильно. b должно было быть в левой части сравнения. Я отредактировал свой вопрос, чтобы исправить

2. отлично работает. Я не понимаю математику, но это работает.

3. Теперь я понимаю цель этой суммы. Сначала вы должны найти значения min и max , затем вы можете рассчитать middle значение как = (a b c) - (max min) .

Метки: