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

[lair]

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

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

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

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

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

[kafeman]

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

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

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

[kafeman]

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

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

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

[vlivyur]

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

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

[kafeman]

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

[zagayevskiy]

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

[zagayevskiy]

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

[GamePad64]

Так-с,

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

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

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

[zagayevskiy]

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

[forgotten]

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

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

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

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

[Vaner]

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

[kafeman]

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

Нет.

при решении этой задачи интересовала именно оптимизация самого алгоритма

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

[lair]

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

[gearbox]

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

[Oxyd]

Яростно плюсую!

[Eleneldil]

Один мой старый знакомый, где-то году в 99-м присутствовал при (да, именно так, сам не он в том проектене кодил) при начале разработки некоего сетевого игрового проекта (который так ине взлетел, но то другая история). Протокол сочиняли сами, ну и команды, посылаемые клиентом, были там просто словами, т.е. короткими строками. Тот мой знакомый, как программист старой (уже на тот момент - "старой") закалки, глядя на это, предложил сделать все строки 4-символьными, чтобы их можно было сравнивать, как 32-битовые целые, что ускорило бы разбор сервером входящих пакетов (вместо сравнений строк и if-else-if..., сделать просто switch по этим числам). Ну и сделал пробный пример. Сравнил скорости. И был очень удивлён отсутствием сколько-то осмысленного выигрыша у своего варианта. Это было на процессорах, которые в 99-м были уже уровня "доступно для маленького стартапа".

Хотя, да, я сам ещё помню времена, когда деление было действительно более дорогой по тактам процессора операцией, чем инкремент.

[MadRogue]

Старый некромант решил на ночь глядя рассказать историю!

[gearbox]

ну давайте понекромансим, чего уж там
деление - алгоритмически более накладная операция чем инкремент/сложение. То есть если тут что то смогут ускорить то это будет фундаментальный прорыв. Соотв. моя рекомендация избегать деление основана на фундаменте математики.

предложил сделать все строки 4-символьными, чтобы их можно было сравнивать, как 32-битовые целые, что ускорило бы разбор сервером входящих пакетов (вместо сравнений строк и if-else-if..., сделать просто switch по этим числам)

этими вещами должен заниматься компилятор. То есть тут Ваш знакомый заложился на архитектуру процессора и тупость компилятора - ни то ни другое не постоянны :)
В общем я к тому что поведение мое и Вашего знакомого внешне похожи но мотивы сильно разные :)

[rostik_tsekhmistro]

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

[manul]

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

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;

[gearbox]

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

[rostik_tsekhmistro]

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

[gearbox]

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

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

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

[manul]

Тогда уж так
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)])

[kafeman]

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

[lair]

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

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

[XAHOK]

С точки зрения результата задача описана верно и даже убрана исходная подсказка (правда я согласен, что в ней была вся соль задачи). Но эта задача мне нравится еще тем, что она легко превращается в веселый квест: сравнить 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 операторов.
Я думаю для других языков/компиляторов ситуация будет похожей. Плюс подвох уже в самой постановки вопроса ожидается. Правда я сомневаюсь, что для собеседования это подходящий вопрос, т.к. мало кто на нервах сразу сообразит, где собака зарыта.

[XAHOK]

Извиняюсь за неточность, но отредактировать комментарий уже не смог: вместо .NET должно быть C#.NET

[lair]

С точки зрения результата задача описана верно и даже убрана исходная подсказка

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

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

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

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

И зачем?..

[XAHOK]

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

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

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

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

И зачем?..

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

[lair]

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

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

[XAHOK]

Вы имеете в виду:

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”.

Или существует еще один вариант?

[lair]

Именно этот вариант я и имею в виду.

[XAHOK]

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

[MadRogue]

Мой вариант написания. По сути все те же 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 и немного поменять условие

[kovalexius]

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

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

[kovalexius]

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

[kovalexius]

Тут два условных оператора и no strings.
В предудыдущем — бага (спешил очень)
если fuzzbuzz нада печатать при других условиях — то решение не подойдет.

[kovalexius]

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

[kafeman]

Если число кратно пятнадцати, то программа должна выводить слово FizzBuzz.

Ваша выводит

Fizz
Buzz

, что совпадает с выводом для конца последовательности (99, 100):

Fizz
Buzz

[kovalexius]

Да? не думал что это принципиально. тогда

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 наверно потратил чтобы полностью реализовать и проверить.
Быдлокодер, похоже, я. Либо пишу быстро код с кучей багов, либо трачу дофига времени.
Как научиться решать такие задачки за приемлемое время?

[kovalexius]

ппц быдлокодер.
я уж хотел написать что инициализацию
std::vector str =…
нада вынести за пределы цикла, хаха
путаюсь в трех строчках кода

[lair]

Как научиться решать такие задачки за приемлемое время?

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