Loading...

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

l000p avatar l000p 13 Точки

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


Благодаря за вниманието. :) 

 

 

1
C++ Fundamentals 16/09/2019 00:04:57
VasAtanasov avatar VasAtanasov 48 Точки

Препоръчвам да прочетете статията

https://www.itexico.com/blog/software-development-kiss-yagni-dry-3-principles-to-simplify-your-life

Колегата kolioi е дал според мен най простото решение на съответния проблем.

Гледам размятат се някви матрици и "pair" за проблем, който е изключително прост. Няма лошо да се тренира човек, ама когато не се изисква нещо по услови не го правете.

1
17/09/2019 09:10:23
spasimira25 avatar spasimira25 25 Точки

Здравей, колега. Без да омаловажавам решението на колегата 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...
Поради спецификата на курса (малко време-, малко задачи) лично аз се опитвам да реша всяка една задача поне по два начина, ако имам време. Явно не само аз де.
Хубав Ден,
Тошо.

1
j.petrov_90 avatar j.petrov_90 373 Точки

Привет, колега,

Много съм щастлив, че ти се занимава толкова и не се страхуваш да експериментираш.
Решил си задачата вярно и това не го оспорвам.

Ще се опитам да дам съвет от моята камбанария:
Ще си призная, не съм прочел статията за 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

Поздрави,
Живко

2
spasimira25 avatar spasimira25 25 Точки

Мерси, коментара на 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 << ' ';} }
}

Още веднъж благодаря за линка.
Хубав Ден,
Тошо.

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.