09.03.2016 11:53
Vaner 25 2700 Источник
При устройстве на работу программистом столкнулся с интересной задачей следующего содержания:

«Напишите программу, которая выводит на экран числа от 1 до 100. При этом вместо чисел, кратных трем, программа должна выводить слово Fizz, а вместо чисел, кратных пяти — слово Buzz. Если число кратно пятнадцати, то программа должна выводить слово FizzBuzz. Задача может показаться очевидной, но нужно получить наиболее простое и красивое решение.»

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

Судя по всему, под очевидным решением предполагается использование в цикле четырех условных операторов. Первый проверяет кратность числа трем, второй пяти, третий пятнадцати, а четвертый выводит число в случае невыполнения первых трех условий. Однако, после первого же прочтения задачи возникает желание избавиться от условия проверки на кратность пятнадцати, так как слова Fizz и Buzz подобраны таким образом, чтобы при одновременном выполнении условий кратности трем и пять можно было вывести FizzBuzz. Таким образом можно обойтись тремя условиями. 

#include <iostream>
using namespace std;
int main()
{
  for(int i=1;i<101;i++)
  {
      if(i%3==0) cout<<"Fizz";
      if(i%5==0) cout<<"Buzz";
      if(i%3!=0 && i%5!=0) cout<<i;
      cout<<endl;
  }
}


Данный код имеет уже три условных оператора и четыре операции сравнения.

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

#include <iostream>
#include <string>
using namespace std;
int main()
{
  for(int i=1;i<101;i++)
  {
      string str="";
      if(i%3==0) str="Fizz";
      if(i%5==0) str+="Buzz";
      if(str=="") str=to_string(i);
      cout<<str+'\n';
  }
}


Этот вариант решения задачи является наиболее распространенным в сети, но на мой взгляд решению по прежнему не хватает изящности и просты, а именно к этому и нужно стремиться согласно условию задачи.
А что если попробовать не приписывать к строке нужный текст, а наоборот убирать текст из строки вида «ЧислоFizzBuzz»?

#include <iostream>
#include <string>
using namespace std;
int main()
{
  for(int i=1;i<101;i++)
  { 
    string n=to_string(i), f = "Fizz", b="Buzz"; 
    if(i%3!=0) f=""; else n=""; 
    if(i%5!=0) b=""; else n=""; 
    cout<<n+f+b+"\n"; 
    }
}


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

Комментарии (25)


  1. lair
    09.03.2016 15:00
    #8799007
    +11

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

    Вы это серьезно?

    Например, с помощью строк можно избавиться от одной операции сравнения.

    А стоимость операций со строками вы не учитываете вообще?

    Ну и да, вы бы все-таки писали результирующую временную сложность (в нотации большого О) для каждого получившегося у вас варианта.


  1. kafeman
    09.03.2016 15:04
    #8799019
    +4

    Мерить эффективность в количестве операторов ветвления?

    if(str=="") str=to_string(i);

    Даже в самой простой реализации strcmp тут будет еще одно условие.


    1. kafeman
      09.03.2016 15:10
      #8799027
      +2

      Хотя… Если сделать

      if (str[0] == '\0')

      То, может, и не увеличится. В любом случае, перевод int в std::string тут неэффективен.


  1. vlivyur
    09.03.2016 15:42
    #8799071
    +5

    Полученный алгоритм содержит всего две операции сравнения и два условных оператора
    И четыре вызова подпрограмм. Что даёт неограниченный потенциал в неучтённых операциях сравнения и циклов.
    FizzBuzz, или почему программисты не умеют программировать


  1. deniskreshikhin
    09.03.2016 15:44
    #8799075
    +1

    На си вроде это самое простое решение:

    main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":0:"Fizz",i);}

    А вообще это бесконечная тема: http://codegolf.stackexchange.com/questions/58615/1-2-fizz-4-buzz


    1. kafeman
      09.03.2016 15:58
      #8799117

      Что есть i? Количество аргументов командной строки? Тогда этот код не всегда будет работать верно...


      1. deniskreshikhin
        09.03.2016 16:12
        #8799151

        Да, ну это не мой код, просто самый короткий из тех что был на си)


    1. zagayevskiy
      09.03.2016 16:02
      #8799127
      +3

      Подскажите, пожалуйста, по какому критерию оно простое?


      1. deniskreshikhin
        09.03.2016 16:11
        #8799147

        По длине -)) Ну вообще не понятно как такая глупая задача как fizz buzz может оцениваться с каких-то алгоритмических позиций


  1. zagayevskiy
    09.03.2016 16:00
    #8799123

    Я бы, как собеседующий, таким решением был огорчён. Когда смотришь на это, вообще не очевидно, что происходит. Я бы попросил вас выводить Fizz, когда делится на 5, Buzz, когда делится на 15, FizzBuzz, когда делится на 2 и число — иначе. Пришлось бы вам полностью ваше решение переписывать, да.


  1. GamePad64
    09.03.2016 16:03
    #8799133
    +4

    Так-с,

    1. using namespace std;
      Невероятное зло. Нет, я понимаю, что во всех дурацких учебниках есть эта строчка, но в реальном коде её использовать очень плохо. Используйте fully-qualified name или импортируйте только то, что вам нужно, а не всё пространство имён, например using cout = std::cout;
    2. Зачем внесли объявление string в тело цикла? allocation/deallocation на каждую итерацию, очень медленно.
    3. Строковые операции — это тоже медленно.

    n. FizzBuzz на хабре? Серьёзно?

    P. S. Первый, "классический" вариант — самый адекватный


    1. zagayevskiy
      09.03.2016 16:23
      #8799185
      +1

      Зато на ифах "сэкономили". Лол.


  1. forgotten
    09.03.2016 16:27
    #8799189
    +5

    Я бы эту задачу рассмотрел с несколько другой стороны. А какое решение является наиболее устойчивым к изменению требований?

    Что, если завтра вместо вывода cout, например, нужно будет делать сетевой запрос? Два отдельных запроса "Fizz" и "Buzz" станут неэквивалентны одному "FizzBuzz", и все эти блестящие оптимизации на уменьшение числа условий выйдут боком.

    Что, если завтра добавится третий, четвёртый пятый вариант, и нужно будет на любую комбинацию делителей выводить какую-то свою строку? Как быстро этот супер-оптимизированный код станет вконец нечитабельным?

    Короче, я бы в этой задаче смотрел на другое. Если кандидат поэкономил условные операторы — попросил бы переписать под новые условия и посмотрел, как он это будет делать.


  1. Vaner
    09.03.2016 17:30
    #8799289
    -5

    Я напишу отдельный комментарий, чтобы не отвечать по отдельности всем, кто высказался по поводу сомнительности использования строк и времени их обработки. Хочу сказать, что в рамках этой статьи я рассматривал поставленную задачу, как задачу оптимизации непосредственно самого алгоритма. Приведенные примеры кода на C++ являются не более чем демонстрацией алгоритма. Если бы я написал примеры реализации алгоритма в виде блок схем, то все вопросы касательно использования строк и отсутствия рассмотрения обработки строк в качестве критерия временной сложности отпали бы. Да, я согласен со всеми полезными исправлениями и замечаниями к коду, спасибо всем большое за это, но меня при решении этой задачи интересовала именно оптимизация самого алгоритма действий, без привязки к конкретной реализации на конкретном языке программирования.


    1. kafeman
      09.03.2016 17:34
      #8799295
      +8

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

      при решении этой задачи интересовала именно оптимизация самого алгоритма
      Такой подход очень трудно назвать словом «оптимизация».


    1. lair
      09.03.2016 21:35
      #8799711
      +4

      Вы когда-нибудь слышали про то, как описывается сложность алгоритма?


  1. gearbox
    10.03.2016 22:03
    #8801133

    за деление в этой задаче надо бить по пальцам. Два счетчика решают проблему и сводят все к инкременту и сравнению целых.


  1. rostik_tsekhmistro
    15.03.2016 16:38
    #8806361

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


  1. Daniro_San
    18.03.2016 07:57
    #8810011

    Уж простите, не удержался от написания такой красоты

    for(int i=1; i<=100; ++i)
    if(!(i%3)||!(i%5))
    std::cout<< (!(i%3)?!(i%5)? «FizzBuzz»:«Fizz»:«Buzz» ) <<std::endl;
    else std::cout<<i<<std::endl;


    1. gearbox
      18.03.2016 14:50
      #8810429

      if(i%3 && i%5) continue;


      1. rostik_tsekhmistro
        18.03.2016 18:53
        #8810711
        -1

        Это не обизательно


        1. gearbox
          18.03.2016 19:50
          #8810755

          не, ну так то и руки мыть перед едой не обязательно. Ранний выход из итерации за счет инверсии условия облегчает запись условия — она становится более читаемой, при этом код, следующий дальше — не меняется, он так же выполняется только при выполнении того условия что в Вашем варианте. При этом если это не однострочник а блок — мы раскрываем блок и уменьшаем степень вложенности в коде. В общем вполне себе распространенный прием в программировании. А вообще у нас на раёне нормальные пацаны так делают:

          for(int i=1, c=1, d=1; i<=100; ++i, ++c, ++d){
    if(3 == c) c = 0;
    if(5 == d) d = 0;
    if(c && d ) std::cout<< i;
    if(!c) std::cout<< «Fizz»;
    if(!d) std::cout<< «Buzz»;
    std::cout <<std::endl;
}

          и никаких делений с остатками и выкрутасов с тернарниками. Потом другие пацаны прийдут — прочитать смогут, предъявлять не будут.


      1. Daniro_San
        19.03.2016 10:09
        #8811113

        Тогда уж так
        for(int i=1; i<=100; ++i)
        if(i%3 && i%5)
        {
        std::cout<<i<<std::endl;
        continue;
        }
        std::cout<< (!(i%3)?!(i%5)? «FizzBuzz»:«Fizz»:«Buzz» ) <<std::endl;
        А как нормальные пацаны отнесуться к этому?
        input([ «FizzBuzz» if not x%3 and not x%5 else «Fizz» if not x%3 else «Buzz» if not x%5 else x for x in range(1, 101)])


        1. kafeman
          19.03.2016 13:54
          #8811201

          Добавьте скобки после for, иначе i всегда 100 будет.


  1. lair
    18.03.2016 22:51
    #8810905

    Напишите программу, которая выводит на экран числа от 1 до 100. При этом вместо чисел, кратных трем, программа должна выводить слово Fizz, а вместо чисел, кратных пяти — слово Buzz. Если число кратно пятнадцати, то программа должна выводить слово FizzBuzz. Задача может показаться очевидной, но нужно получить наиболее простое и красивое решение.

    Вообще, надо заметить, что здесь изрядно переврано исходное условие задачи.