Pull to refresh

Программирование без использования условных конструкций

Abnormal programming *
Sandbox
Один знакомый заявил мне, что любая программа может быть написана без использования if/else. Я, конечно, тут же возмутился и сформулировал ему (а заодно и себе) простейшую задачу: написать программу, которая будет радоваться, если на вход ей подать, например, слово «печенька», и огорчаться в противном случае; но при этом нельзя использовать никаких конструкций, изменяющих направление программы — то есть она должна быть строго линейной. Решение под катом.

Псевдоправильные решения

Свою версию решения я реализовал на Java. Поэтому, наверное, первой моей мыслью должно было стать использование полиморфизма. Но, честно говоря, как применить этот принцип к данной задаче, не понимаю до сих пор. Возможно, необходимо определить метод в классе String и переопределить его для объекта "cake"? К сожалению на Java такое нереализуемо.

Настоящей первой мыслью было, раз без if'а не обойтись, надо использовать что-нибудь библиотечное, что может стать его заменой. Выбор пал на Hashtable.

Первый блин:
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String input = in.readLine();
    HashMap<Boolean,String> map = new HashMap<Boolean,String>();
    map.put(true, "Yummy!!!");
    map.put(false, "The cake is a lie :(");
    System.out.println(map.get(input.equals("cake")));

Вроде бы условия задачи выполнены. Но позвольте, equals(), это ли не откровенное жульничество? Ведь по сути своей он именно через if/else и реализуется! Что ж, можно обойтись и без него. А заодно и без булевых значений. Надо лишь прокрутить значения в HashMap два раза:
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String input = in.readLine();
    Object yeah = new Object();
    HashMap map = new HashMap();
    map.put("cake", yeah);
    map.put(yeah, "Yummy, thanks!!!");
    map.put(null, "You are still lying to me!");
    System.out.println(map.get(map.get(input)));

А если это реализовать на другом языке, в котором хеш-таблицы вшиты в синтаксис, так задача и вовсе превратится в однострочник. Идеально ли это решение? Я считаю, что всё-таки нет. Ведь внутренняя реализация хеш-таблицы просто необходимо будет использовать условные конструкции для нахождения ключа. А нельзя ли обойтись без них?

Универсальное решение

Для того, чтобы построить верное решение, подходящее для любого языка, нужно идти не вверх в абстракции, а вниз — к числам. Что у нас останется? Ну конечно математические операции! На языке математики условие if x then a else b можно записать как x*a+(1-x)*b (полагая, разумеется, что истина это 1, а ложь — 0). Тогда для решения задачи достаточно лишь написать функцию, равную 1 для строки «cake» (или «cookie», или «candy»), и 0 в остальных случаях. Вывод сообщения при этом может выглядеть так:
    int x = isCake(input);
    System.out.print((char)(x*'Y'+(1-x)*'N'));
    System.out.print((char)(x*'e'+(1-x)*'o'));
    System.out.print((char)(x*'s'));

При написании характеристической функции для тортика стоит учесть, что длина строки есть величина переменная, но без операций ветвления мы не можем проверить произвольное число символов. Выход прост: дополним строку пятью нулями (гарантируя, что в ней как минимум пять символов) и проверим, что первые пять символов это "cake\0". Итог:
import java.io.*;

class CakeEater {
    static public void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String input = in.readLine().concat("\0\0\0\0\0");
        int x = input.charAt(0)^'c';
        x |= input.charAt(1)^'a';
        x |= input.charAt(2)^'k';
        x |= input.charAt(3)^'e';
        x |= input.charAt(4);
        //дальше несколько утомительный фокус, чтобы превратить ненулевое число в 1
        x = x | (x>>1) | (x>>2) | (x>>3) | (x>>4) | (x>>5) | (x>>6) | (x>>7) | (x>>8)
          | (x>>9) | (x>>10) | (x>>11) | (x>>12) | (x>>13) | (x>>14) | (x>>15);
        x = 1 - (x&1);
        System.out.print((char)(x*'Y'+(1-x)*'N'));
        System.out.print((char)(x*'e'+(1-x)*'o'));
        System.out.println((char)(x*'s'));
    }
}

Вывод: простейшую программу без использования if/else написать можно, но уже она становится громоздкой. А попробуйте написать линейную программу, вычисляющую, например, факториал!
Tags:
Hubs:
Total votes 83: ↑56 and ↓27 +29
Views 30K
Comments Comments 161