Решение задачи FizzBuzz

При устройстве на работу программистом столкнулся с интересной задачей следующего содержания:

«Напишите программу, которая выводит на экран числа от 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"; 
    }
}


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

Comments 43

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

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

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

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

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

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

      Даже в самой простой реализации strcmp тут будет еще одно условие.
        +2
        Хотя… Если сделать

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

        То, может, и не увеличится. В любом случае, перевод int в std::string тут неэффективен.
        +5
        Полученный алгоритм содержит всего две операции сравнения и два условных оператора
        И четыре вызова подпрограмм. Что даёт неограниченный потенциал в неучтённых операциях сравнения и циклов.
        FizzBuzz, или почему программисты не умеют программировать
          +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
            0
            Что есть i? Количество аргументов командной строки? Тогда этот код не всегда будет работать верно...
              0
              Да, ну это не мой код, просто самый короткий из тех что был на си)
              +3
              Подскажите, пожалуйста, по какому критерию оно простое?
                0
                По длине -)) Ну вообще не понятно как такая глупая задача как fizz buzz может оцениваться с каких-то алгоритмических позиций
              0
              Я бы, как собеседующий, таким решением был огорчён. Когда смотришь на это, вообще не очевидно, что происходит. Я бы попросил вас выводить Fizz, когда делится на 5, Buzz, когда делится на 15, FizzBuzz, когда делится на 2 и число — иначе. Пришлось бы вам полностью ваше решение переписывать, да.
                +4
                Так-с,

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

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

                P. S. Первый, "классический" вариант — самый адекватный
                  +1
                  Зато на ифах "сэкономили". Лол.
                  +5
                  Я бы эту задачу рассмотрел с несколько другой стороны. А какое решение является наиболее устойчивым к изменению требований?

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

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

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

                      при решении этой задачи интересовала именно оптимизация самого алгоритма
                      Такой подход очень трудно назвать словом «оптимизация».
                        +4
                        Вы когда-нибудь слышали про то, как описывается сложность алгоритма?
                        0
                        за деление в этой задаче надо бить по пальцам. Два счетчика решают проблему и сводят все к инкременту и сравнению целых.
                        0
                        В принципе задача не сложная и тремя условиями можно вполне обойтись. И время работы будет даже больше при использовании строк, да и просто зачем усложнять задачу.
                          0
                          Уж простите, не удержался от написания такой красоты

                          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;
                            0
                            if(i%3 && i%5) continue;
                              –1
                              Это не обизательно
                                0
                                не, ну так то и руки мыть перед едой не обязательно. Ранний выход из итерации за счет инверсии условия облегчает запись условия — она становится более читаемой, при этом код, следующий дальше — не меняется, он так же выполняется только при выполнении того условия что в Вашем варианте. При этом если это не однострочник а блок — мы раскрываем блок и уменьшаем степень вложенности в коде. В общем вполне себе распространенный прием в программировании. А вообще у нас на раёне нормальные пацаны так делают:

                                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;
                                }

                                и никаких делений с остатками и выкрутасов с тернарниками. Потом другие пацаны прийдут — прочитать смогут, предъявлять не будут.
                                0
                                Тогда уж так
                                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)])
                                  0
                                  Добавьте скобки после for, иначе i всегда 100 будет.
                              0
                              Напишите программу, которая выводит на экран числа от 1 до 100. При этом вместо чисел, кратных трем, программа должна выводить слово Fizz, а вместо чисел, кратных пяти — слово Buzz. Если число кратно пятнадцати, то программа должна выводить слово FizzBuzz. Задача может показаться очевидной, но нужно получить наиболее простое и красивое решение.

                              Вообще, надо заметить, что здесь изрядно переврано исходное условие задачи.
                                0
                                С точки зрения результата задача описана верно и даже убрана исходная подсказка (правда я согласен, что в ней была вся соль задачи). Но эта задача мне нравится еще тем, что она легко превращается в веселый квест: сравнить 2 очень похожих реализации алгоритма с использованием любых инструментов.

                                Каноничное:

                                if(i%3==0) cout<<«Fizz»;
                                if(i%5==0) cout<<«Buzz»;
                                if(i%3!=0 && i%5!=0) cout<<i;
                                cout<<endl;

                                Альтернативное:

                                if(i%3==0) cout<<«Fizz»;
                                if(i%5==0) cout<<«Buzz»;
                                else if(i%3!=0) cout<<i;
                                cout<<endl;

                                Например, для .NET оба варианта дадут идентичный итоговый результат, после генерации кода. Правда при одном маленьком, но очень важном условии: если собирать с конфигурацией Release, т.к. компилятор развернет else if в каноничный вариант, что легко увидеть, если посмотреть IL-код. А вот вариант при сборке с конфигурацией Debug будет различаться. В данном случае второй вариант будет короче на 7 байт и 6 операторов.
                                Я думаю для других языков/компиляторов ситуация будет похожей. Плюс подвох уже в самой постановки вопроса ожидается. Правда я сомневаюсь, что для собеседования это подходящий вопрос, т.к. мало кто на нервах сразу сообразит, где собака зарыта.
                                  0
                                  Извиняюсь за неточность, но отредактировать комментарий уже не смог: вместо .NET должно быть C#.NET
                                    0
                                    С точки зрения результата задача описана верно и даже убрана исходная подсказка

                                    Это не подсказка, в том-то и дело. FizzBuzz — это задача без подвоха.

                                    вместо .NET должно быть C#.NET

                                    В C#.net есть cout и << в том значении, в котором вы его употребили?

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

                                    И зачем?..
                                      0
                                      Это не подсказка, в том-то и дело. FizzBuzz — это задача без подвоха.

                                      Это намек на преждевременную оптимизацию

                                      В C#.net есть cout и << в том значении, в котором вы его употребили?

                                      Есть Console.Write, но для сохранения общей стилистики я использовал оригинальную нотацию.

                                      И зачем?..

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

                                        Неа. В оригинальной задаче никакого намека нет. Там все правда просто.
                                          0
                                          Вы имеете в виду:

                                          Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

                                          Или существует еще один вариант?
                                            0
                                            Именно этот вариант я и имею в виду.
                                              0
                                              Я, когда в первый раз столкнулся с данной задачей, зацепился взглядом за условие для FizzBuzz. И первая мысль была о том, что именно тут заложен подвох, а оказалось, что это и есть решение задачи.
                                  –1
                                  Мой вариант написания. По сути все те же 3 сравнения и 1 операция (сложения).
                                  Правда на php, на на си примерно так же будет выглядеть:

                                  $list = array("", "Fizz", "Buzz", "FizzBuzz");
                                  for($i = 1; $i <= 100; ++$i) {
                                  	$index = (($i % 3)?0:1) + (($i % 5)?0:2);
                                  	echo ($index > 0?$list[$index]:$i).' ';
                                  }
                                  


                                  Можно избавиться от пустого элемента массива, но тогда нужно будет вычитать 1 из $index и немного поменять условие
                                    –1
                                    for(int i = 0; i <= 100; i++)
                                    {
                                        if(i%3 == 0)
                                           std::cout << "Fizz" << std::endl;
                                        if(i%5 == 0)
                                        {
                                           std::cout << "Buzz" << std::endl;
                                           continue;
                                        }
                                        std::cout << i << std::endl;
                                    }
                                    

                                    два условных оператора, два оператора сравнения и никаких телодвижений со строками
                                      –2
                                      for(int i = 0; i <= 100; i++)
                                      {
                                          if(i%15 == 0)
                                          {
                                             if(i%3 == 0)
                                                 std::cout << "Fizz" << std::endl;
                                             else
                                                 std::cout << "Buzz" << std::endl;
                                             continue;
                                          }
                                          std::cout << i << std::endl;
                                      }
                                      
                                        0
                                        Тут два условных оператора и no strings.
                                        В предудыдущем — бага (спешил очень)
                                        если fuzzbuzz нада печатать при других условиях — то решение не подойдет.
                                        0
                                        for(int i = 0; i <= 100; i++)
                                        {
                                            if(i%3 == 0)
                                            {
                                               std::cout << "Fizz" << std::endl;
                                               if(i%5 == 0)
                                                   std::cout << "Buzz" << std::endl;
                                               continue;
                                            }
                                            if(i%5 == 0)
                                            {
                                               std::cout << "Buzz" << std::endl;
                                               continue;
                                            }
                                            std::cout << i << std::endl;
                                        }
                                        
                                          0
                                          Если число кратно пятнадцати, то программа должна выводить слово FizzBuzz.
                                          Ваша выводит
                                          Fizz
                                          Buzz
                                          , что совпадает с выводом для конца последовательности (99, 100):
                                          Fizz
                                          Buzz
                                            0
                                            Да? не думал что это принципиально. тогда
                                            for(int i = 0; i <= 100; i++)
                                            {
                                                if(i%3 == 0)
                                                {
                                                   std::cout << "Fizz";
                                                   if(i%5 == 0)
                                                       std::cout << "Buzz";
                                                   std::cout << std::endl;
                                                   continue;
                                                }
                                                if(i%5 == 0)
                                                {
                                                   std::cout << "Buzz" << std::endl;
                                                   continue;
                                                }
                                                std::cout << i << std::endl;
                                            }
                                            


                                            А еще так можно, со строками уже с этим дурацкими:
                                            #include <iostream>
                                            #include <vector>
                                            #include <string>
                                            
                                            int main()
                                            {
                                                for(int i = 1; i <= 100; i++)
                                                {
                                                    std::vector<std::string> str = {std::to_string(i), "Fizz", "Buzz", "FizzBuzz"};
                                                    int ind = !(i%3) + (!(i%5)) * 2;
                                                    std::cout << str[ind] << std::endl;
                                                }
                                            }
                                            


                                            Не правда ли изящно? (C++11 нужен)

                                            Но не за 5 минут последнее решение реализовал. Сначала крутилась в голове чего то, потом только сформулировал принцип и алгоритм. Где то минут 10 — 15 наверно потратил чтобы полностью реализовать и проверить.
                                            Быдлокодер, похоже, я. Либо пишу быстро код с кучей багов, либо трачу дофига времени.
                                            Как научиться решать такие задачки за приемлемое время?
                                              0
                                              ппц быдлокодер.
                                              я уж хотел написать что инициализацию
                                              std::vector str =…
                                              нада вынести за пределы цикла, хаха
                                              путаюсь в трех строчках кода
                                                0
                                                Как научиться решать такие задачки за приемлемое время?

                                                1. Перестать пытаться решить их быстро.
                                                2. Начать сначала писать тесты.

                                          Only users with full accounts can post comments. Log in, please.