Most Frequent Number C++ Fundamentals
Здравейте, тази задача доста ме "озори", но най-после открих решение.
https://pastebin.com/X0nnFh54-Решение
https://judge.softuni.bg/Contests/Compete/Index/1349#3-Judge
https://softuni.bg/trainings/resources/officedocument/42363/homework-problem-descriptions-c-plus-plus-fundamentals-september-2019/2402- Условие, намира се на 4-та позиция.
Пиша темата, за да открия по-елегантен или рационален начин за решение. Това което най-много ме затормозява е как щях да я реша ако числата не бяха от 0 до 9? По моето решение с още някой друг ред може да се случи, но няма ли да изконсумира прекалено много ресурс от машината ??
Това което искам да видя е най-икономичното решение от гледна точка на обработка, което имплементира само познатите ни за сега структори от данни (array & vector).
Благодаря за вниманието. :)
Здравей, колега. Без да омаловажавам решението на колегата kolioi , което е много елеганто (ако мога така да се изразя) то също не е по условие. Т.е никъде в условието на задачата не се иска да се реши с масив. Реално, ако трябва да спазваме "KISS" - решението е още по-просто и глупаво. Може да се реши и без знанията за масиви, вектори, мапове итн итн. Всъщност може да се реши и без знанията за цикли. Дал съм го по-назад, но тъй като трябва да разгърнеш отговор, ще го пейстна тук леко орязано, все едно че търсим до числото 3, а не до 9.
#include<iostream>
int main(){
int counter_max=0, counter1=0, counter2=0, counter3=0; //...etc
int how_many_integers=0;
std::cin>>how_many_integers;
int number=0;
for(int i=0 ; i<how_many_integers; i++){
std::cin>>number;
if (number==1){counter1++; if (counter1>=counter_max){counter_max=counter1;} }
if (number==2){counter2++; if (counter2>=counter_max){counter_max=counter2;} }
if (number==3){counter3++; if (counter3>=counter_max){counter_max=counter3;} }
//... etc
}
if (counter1==counter_max){std::cout<<1<<" ";}
if (counter2==counter_max){std::cout<<2<<" ";}
if (counter3==counter_max){std::cout<<3<<" ";}
//....etc
}
Предоплагам, ще се съгласиш, че е грозно. Нищо, че е мега KISS. От тук натам следва някаква оптимизация. Решението с 1 масив на колегата kolioi , решение с 2 масива (моето и на колегата BozhidarKlouchek ), решение с 1 двоен масив и т.н. Вчера имах малко повече време и реших да компилирам 4-5 различни варианта. Решението KISS се справи по-бавно и с повече обем памет от решението с два масива. Явно е поради кеш оптимизацията на процесорите, когато работят с масиви - не знам.
В края на краищата, всички сме си решили задачите, а сега си говорим if-else...
Поради спецификата на курса (малко време-, малко задачи) лично аз се опитвам да реша всяка една задача поне по два начина, ако имам време. Явно не само аз де.
Хубав Ден,
Тошо.
Привет, колега,
Много съм щастлив, че ти се занимава толкова и не се страхуваш да експериментираш.
Решил си задачата вярно и това не го оспорвам.
Ще се опитам да дам съвет от моята камбанария:
Ще си призная, не съм прочел статията за KISS, но ще се опитам да разгадая за какво става дума от контекста на дискусията.
Под KISS в случая се няма на предвид да се реши задачата с минимално знания (без масиви, вектори) и т.н.
По-скоро се има предвид да се реши задачата най-просто. Т.е. ако аз съм програмист, който гледа този код - да го погледна за 5 секунди и да разбера точно какво прави.
1) Няма нужда да се съзванат 10 променливи, като можеш да направиш един масив от 10 променливи.
2) Няма нужда от 10 if statement-а. (Само за схравка, ако се ползваще това решение неща поне са "else if")
3) множеството if-ове определено правят кода неимоверно по-бавен. Това не можеш да го засечеш, защото програмата е прекалено малка, че за да има значение изобщо как си я решил като скорост. Накрая, но не на последно вясто Judge определено не е най-точната система за отмерване на скорост на решение на задачата.
Все пак, признавам, че успя да ме впечатлиш с интересния си подход с многото if-ове.
Поради тази причина ще споделя една статия, която описва, защо if-овете реално ще забавят кода.
Материята в нея изисква доста повече знания в света на програмирането, но това не пречи на човек да я прочете и усмисли.
Розгледай въпроса на автора и най-вече обяснението на коментара с най-много vote-ове.
https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
Поздрави,
Живко
Мерси, коментара на stackoverflow (потребителя с 30к+ гласа) ми беше полезен, че ми отговори на поне два въпроса. Първия - защо тази задача е по-добре да се реши с два масива (oткъм скорост), отколкото с един + спиране за изчакване на нов вход. И втория - за клоновите проверки т.е. ако има "if if if" ще е по-бавно отколкото "if else-if else-if". Но в тази задача, въпреки че е по-бързо, ако се ползва "else-if" тя няма да работи. Ще прави проверка само за първото повторение и/или ще го печата само него. При този вход: 11 7 7 7 0 2 2 2 0 9 9 9 С Else-if печата само 2. Това си остава едно доста грубо решение. Споделих го само заради статията за KISS - Keep It Simple & Stupid. Симпъл ми звучи добре, но stupid, май ми идва в повече :) Аз лично си харесвам повече другите ми решения. Например това:
#include <iostream>
void input_function(int input_array[], int size_array);
void output_function(int output_array[], int size_array,int max_frequency_counter);
int main()
{
int size_array=0;
int max_frequency_counter = 0;
std::cin>>size_array;
int my_array[size_array]{};
input_function(my_array, size_array);
int frequency_array[10] {};
for (int i = 0; i < size_array; ++i){
int n;
n=my_array[i];
frequency_array[n]++;
}
for (int i = 0; i < 10; ++i)
if (max_frequency_counter < frequency_array[i]) {max_frequency_counter = frequency_array[i];}
output_function(frequency_array, 10, max_frequency_counter);
return 0;
}
void input_function(int input_array[], int size_array){
for(int i=0; i<size_array; i++){
std::cin>>input_array[i];
}
}
void output_function(int output_array[], int size_array,int max_frequency_counter){
for (int i = 0; i < 10; ++i){
if (output_array[i] == max_frequency_counter){
std::cout << i << ' ';} }
}
Още веднъж благодаря за линка.
Хубав Ден,
Тошо.