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

в 11:53, , рубрики: c++, алгоритм FizzBuzz, Алгоритмы, задача FizzBuzz, Программирование, решение 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"; 
    }
}

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

Автор: Vaner

Источник

Поделиться новостью

* - обязательные к заполнению поля