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
kolioi avatar kolioi 641 Точки

Доста излишни неща имаш в кода. Ето ти едно по-просто решение. Ако не знаеш предварително колко е броят на числата (или обектите които броиш) се използва std::map

#include <iostream>
int main()
{
	using namespace std;

	int length;
	cin >> length;

	int frequency[10] = {0};
	for (int i = 0; i < length; ++i)
	{
		int n;
		cin >> n;
		frequency[n]++;
	}

	int max_frequency = 0;
	for (int i = 0; i < 10; ++i)
		if (max_frequency < frequency[i])
			max_frequency = frequency[i];

	for (int i = 0; i < 10; ++i)
		if (frequency[i] == max_frequency)
			cout << i << ' ';

	return 0;
}

 

2
l000p avatar l000p 13 Точки

Благодаря!

0
spasimira25 avatar spasimira25 25 Точки

Решението си ти е идеално. Аз съм го написал по един много дървен начин, който като гледам в джъдж печеля време. Всичко е 0.000. От друга страна губя памет - решението ми е 1.82Mb. Което ме навежда на мисълта, че може да се печели време за сметка на обема...  А иначе самата задача може да се реши и без знания за вектори и масиви. Колкото и да е странно при решение без масив - изгубих и памет и време :) :) :)

0
l000p avatar l000p 13 Точки

Може ли да видя твоето решение?

0
spasimira25 avatar spasimira25 25 Точки

Извинявай, много за забавянето. Просто умувах върху първоначалния въпрос и бях лекинко подивял, че не излиза така както си го мислех. Все пак решението си излезе. Не ти трябва мап (май ще го учим по-натам) и вектор дори не ти трябва.  Само трябва малко по-различен ред на деклариране и дефиниране + 2 цикъла в повече. Май. Минава 100/100 (0.000s; 1.82Mb) + добвената фунционалност за всички инт числа, без отрицателните разбира се. Извини ме за стила на писане ето кода.

#include <iostream>
using namespace std;
int main()
{
    int max_size=0;
    int size_array=0;
    cin>>size_array;
    int my_array[size_array];
        for(int i=0 ; i<size_array ; i++){
            cin>>my_array[i];
        }
/// Не знам, ако тук сее вкара още един фор, за да се открие максимално въведено число
/// дали няма после то да може да се запише във масива с честотите, като максимално...
/// frequency counter да е до 12....15 или повече, съответно и последващите цикли да са до
/// това число
    for(int i=0 ; i<size_array ; i++){
            if (my_array[i]>max_size){max_size=my_array[i];}
        }
     //   cout<<"Current max size is: "<<max_size<<endl;

    int frequency_array[max_size+1] = {0};
        for (int i = 0; i < size_array; ++i){
            int n;
            n=my_array[i];
            frequency_array[n]++;
            }

    int max_frequency_counter = 0;

    for (int i = 0; i < (max_size+1); ++i)
        if (max_frequency_counter < frequency_array[i]) {max_frequency_counter = frequency_array[i];}

 

    for (int i = 0; i < (max_size+1); ++i){
        if (frequency_array[i] == max_frequency_counter){
            cout << i << ' ';} }

 

    return 0;

}

 

0
spasimira25 avatar spasimira25 25 Точки

В първия for си запълвам масива с произволни цифрички; втория фор рови из тея цифри да види, коя е най-голяма, че да я постави като горен край на цикъла за търсене на най-често срещаните числа. Т.е имам два масива,а не само този за най-често срещани числа. Опс, значи  и + 1 масив, спрямо нормалното решение. Ей сега ще пусна и едно решение без масиви даже :) :) :)
Горната граница е +1, е защото трябва да рови от 0-11 да речем, и това са общо 12 цифрички. Или можех да  я сложа <= ... вместо <...
 

 

 

0
16/09/2019 15:31:44
Ilia.M avatar Ilia.M 4 Точки

Здравейте,

За да не отварям нова тема, ще си позволя да ползвам темата на колегата.

От няколко часа се опитвам да реша същата задача,но единствено стигам до 80 точки.

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

След това ползвам функцията sort от stl библиотеката algorithm, за да ги подредя по големина.

Ето сорс кода: 

https://pastebin.com/8tCxPK3L

Проблема е че винаги печатам първото число от масива, независимо дали е най-често срещано или не. Опитах се да го оправя като задам различни начални стойности на броячите (int countNumbers; int mostFrequentNumber;), но тогава в judge става абсолютно мазало.

Ще може ли да ми обясните къде греша?

Благодаря предварително!

0
16/09/2019 13:16:46
l000p avatar l000p 13 Точки

Здравей колега, първо направи си arrSize=10, за да разбереш това което ще ти напиша. 
0 1 2 3 4 5 6 7 8 9 index - това са ти индексите в арейа
2 2 1 3 0 3 1 0 1 0 value - това ти е какво се съдържа в всеки индекс
Ако въведеш примерен код :

13

0 0 1 1 2 3 3 3 5 5 5 6 8

И ръннеш дебъгера  -  гледай внимателно какво става с вложените ти цикли и следващите 2 проверки, сигурен съм, че ще успееш да оправиш кода. :)

0
Ilia.M avatar Ilia.M 4 Точки

Благодаря за съдействието ! Успях да го направя като  "map-вам" честотата на всяко число в масив, Аз се опитвах да го направя за всякакви целочислени числа, но логиката нещо ми куцаше.

0
BozhidarKlouchek avatar BozhidarKlouchek 24 Точки

Такам, тази тема вече получи доста добри отговори, но много исках да се опитам да напиша програма, която ползва само знания array/vector от лекцията, както спомена питането на колегата и естествено без лимита числата да са от 0 до 9. Затова измислих от 0 до безкрайност.

Има начин да се оптимизира, сигурен съм, но, ако е тъпо и работи, не е тъпо, кодче: https://pastebin.com/uBCSjn1T

Идеята е, че имам два масива - original и frequency. В original (шокиращо) запзвам оригиналните стойности от input, а пък в frequency, тяхната честота.
Примерно, ако orginal е 
10 (lenght)

6 2 2 3 5 12 7 9 9 4

то тогава имам два пъти 2ки и два пъти 9ки, и по една 6, 3, 5, 12, 7 и 4.

В frequency масива искам всеки индекс да представя число от original масива, а самата стойност вързана към той индекс да бъде честотата на това число.

Следователно, frequency ще е 

frequency[0]=0   (Понеже няма нули)
frequency[1]=0   (Понеже няма единици)
frequency[2]=2   (Понеже има две двойки)
frequency[3]=1    
frequency[4]=1
frequency[5]=1
frequency[6]=1
frequency[7]=1
frequency[8]=0
frequency[9]=2   (Понеже има две деветки)
frequency[10]=0
frequency[11]=0
frequency[12]=1

Важно е да вметна, че ако в original се добави някое грамадно число от сорта на 10 000 000, осъзнавам че масив frequency ще трябва да стигне индекс 10 000 000, което е доста тегаво, но иначе идеята да ползвам индексите като начин да запомня числата от original ми хареса.

И да де, след това откривам коя стойност на frequency е най-голяма със стандартен алгоритъм, и след това с цикъл извеждам всеки индекс, който е с тази стойност.

В моя пример най-голямата стойност би била 2, следователно се отпечатват 2 и 9, защото това са индексите вързани към числото 2.

Ще ми е интересно да се опитам да оптимизирам кода и да добавя опция за отрицателни числа, защото за жалост отрицателни индекси са нечувана приказка (поне за мен).

Всичко най-хубаво
Божко

0
spasimira25 avatar spasimira25 25 Точки

Горе, долу и аз така. Малко по-назад. До колкото виждам имаме леки разлики. Намирам дължината на frequency масива с още един фор от оригиналния масив. И не вадя първото писане извън фор-а. Не видях някаква разлика в скоростите...
Мислех за отрицателните - един иф (+) елс(-) и един абс при(-), който да записва в  трети (и четвърити) масив за отрицателните, който вече пак ще са положителни...Стори ми се прекалено завързано...

0
BozhidarKlouchek avatar BozhidarKlouchek 24 Точки

Измислих и го как става и отрицателни цифри! Вече би трябвало програмата да работи с всички цифри без ограничението на знака пред цифрата.

Реално ти ползвах идеята spasimira25, създадох съвсем нов масив за отрицателни цифри, който ги превръща в положителни и работи по абсолютно същия начин като положителния масив. Просто при изкарване на конзолата добавям един минус отпред, за да се знае че са отрицателни.

Деликатният момент беше, че след като и двата масива се напълнят трябва човек да съобрази, че програмата все още третира двата масива като различни и извежда поотделно най-често срещаните цифри от положителния и отрицателния масив, но с една проверка накрая всичко става точно. Проверката проверява по колко е максимумът на всеки масив, защото примерно, ако положителният масив има три еднакви цифри, а отрицателният само две, то тогава отрицателният даже не бива да се зачете.

Кодче: https://pastebin.com/2xEpCZ5x

Иначе, проверих програмата в Judge и си я хареса, но ми е ясно, че тя проверява само с от 0 до 9, така че е вероятно да съм изпуснал нещо и някой бъг да ми трови живота без да съм забелязал, но я тествах с lenght на original масива 1 и още няколко частни случай и изглежда сякаш всичко е наред, но ако някой открие грешка, ще съм им благодарен да сподели!

Всичко най-хубаво!
Божко

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

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

Браво за усилията.
Браво на всички включили се в темата - големи пичове сте.

За да се реши задачата с неизвествен range от чилса и само със знанията от array/vector е невъзможно (или ако кажем, че е възможно би било адски глупано да изхабим 2 самосвала RAM за да направил vector с такава огромна големина).

Решението на задачата ще дойде естествено лесно след като по-късно през курса ичим за асоциативни масиви (или така наречените "map"-ове в C++).

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

0
marki02 avatar marki02 1 Точки

Колега,

Окуражавам те да прочетеш ето тази малка статийка за конструкцията pair - много е полезна и е сравнително простичка:
https://www.geeksforgeeks.org/pair-in-cpp-stl/

Първото решение, за което се сетих беше с масив/вектор от pair-и, като в първата клетка на pair-a държиш числото, а във втората държиш броя на пътите, в които то се е срещало. Ето ти първия вид решение: 
https://pastebin.com/TudftASZ

Но все пак видях, че желаеш решение само с вектори/масиви за по-генералния случай, така че единият вариант, за който се сетих е с двумерен масив - много подобно на решението с pair-ите. Общо взето в горната клетка пазиш числото, а в долната - броя пъти, в които си го срещнал. Това е решението с двумерен масив:
https://pastebin.com/ebUqTh9X
А ако искаш да става динамично и не искаш да слагаш някаква константа за бр. клетки - еквивалентът е с вектор от вектори (или още по-добре - вектор от тип pair<int, int>).

И последният вариант, който мога да ти предложа е с единичен вектор, при който всяка четна клетка ти е числото, а всяка нечетна - броят на пътите, в които числото от предната клетка се среща. Т.е. първото число ти е в клетка №0, а counter-а ти за това число е в клетка №1, после - второто ти число е в клетка №2, а counter-а ти за това число е в клетка №3 и т.н. Генерално: i-тото ти число е в клетка № (2*i - 2), а в клетка № (2*i - 1) ти се намира броя на срещанията му. Ето го и това решение:
https://pastebin.com/HjQp9nYT

Сложил съм и коментари за по-лесно разчитане на кода. 
Успех!
 

0
16/09/2019 22:34:12
BozhidarKlouchek avatar BozhidarKlouchek 24 Точки

О мале това е златна мина, благодаря ти! 
Никога преди не бях чувал за pair, това наистина е много полезно!

0
16/09/2019 23:10:01
j.petrov_90 avatar j.petrov_90 373 Точки

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

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

Избягвай да ползваш глобални променливи.
Използвай локални променливи, които придаваш като аргументи на функциите ти.
Глобалните променливи изглеждат "бързия и лесен начин" да си накодиш решението за задача от такъв малък калибер.
Те ще са твоя враг, когато започнеш да пишеш истински програми и гарантирано ще доведат до "мазало" или така наречения "спагети код".
Добрите практики, обаче е хубаво човек да започне да се учи от рано на тях.

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

0
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
DimitarKazakov avatar DimitarKazakov 17 Точки

Ето един код и от мен колеги. Бих искал да чуя вашето мнение за рационализация на кода спрямо тази логика. 

https://pastebin.com/NAS8WTif

0
RadostinStoychev avatar RadostinStoychev 128 Точки

Здравейте колеги, опитах се да я реша по-универсално, за да работи за всякакви числа от тип int, използвах вложени цикли, вектор и сортировка на вектора, но 2рия тест в judge гърми. Опитах най-различни входове и всичко изглежда нормално. Ето задачката: https://pastebin.com/YYpzcsre. Някаква идея защо гърми? Благодаря :)

1
kolioi avatar kolioi 641 Точки

Програмата ти не работи правилно, ако всичките числа са различни, например

3
1 2 3

 

1
RadostinStoychev avatar RadostinStoychev 128 Точки

Ooo да, трябва да принтна и 3ката, благодаря ти много kolioi

0
RadostinStoychev avatar RadostinStoychev 128 Точки

Сложил съм arr_length - 1, а е трябвало да е просто arr_length на единия цикъл. Благодаря още веднъж. Ето и решението ако на някой му е полезно: https://pastebin.com/1H0vj2Yc . Вече минава 100/100 в judge.

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