Помогите с задачкой. Не могу придумать алгоритм.
Пусть последовательность является неубывающей. Определите количество элементов, которые появляются в этой последовательности более k раз, значение k вводится с клавиатуры. Последовательность считывается из файла.
Вот начало кода.
Какой алгоритм нужно сделать?
Вот начало кода.
Код:
int _tmain(int argc, _TCHAR* argv[])
{
FILE*f;
double k;
int count = 0;
int err;
err=fopen_s(&f, "D:\\posled.txt", "r");
if (err)
{
printf_s ("no files \n")
}
return;
while (fscanf_s (f, "%lf", &d)==1)
{
printf_s ("Enter the number of repeat elements: \n")
scanf_s ( "%d", &k)
return 0;
}
{
FILE*f;
double k;
int count = 0;
int err;
err=fopen_s(&f, "D:\\posled.txt", "r");
if (err)
{
printf_s ("no files \n")
}
return;
while (fscanf_s (f, "%lf", &d)==1)
{
printf_s ("Enter the number of repeat elements: \n")
scanf_s ( "%d", &k)
return 0;
}
алгоритм программы следующий.
переменные для работы программы
i - счетчик появления элемента в последовательности
i1 - счетчик элемнетов удовлетворяющих заданному условию.
k - как и в задании - поличество повторений эелемента.
tmp1, tmp2 - пригодится
i1:=0; обнуляем счетчик элементов удовлетворяющиз условию задания
i:=1;
читаем из файла перв. элемент в tmp2;
открываем цикл пока не конец файла{
читаем из файла элемент в tmp1;
если tmp1==tmp2 тогда i++
иначе{
если i>=k тогда i1++;
tmp2:=tmp1;
i:=1;
}
}
если i>=k тогда i1++;
печатаем на экран (колво элементов удовлетворяющих условию задания равно i1 )
все.
на С++ думаю переведете (давно уже не пишу)
переменные для работы программы
i - счетчик появления элемента в последовательности
i1 - счетчик элемнетов удовлетворяющих заданному условию.
k - как и в задании - поличество повторений эелемента.
tmp1, tmp2 - пригодится
i1:=0; обнуляем счетчик элементов удовлетворяющиз условию задания
i:=1;
читаем из файла перв. элемент в tmp2;
открываем цикл пока не конец файла{
читаем из файла элемент в tmp1;
если tmp1==tmp2 тогда i++
иначе{
если i>=k тогда i1++;
tmp2:=tmp1;
i:=1;
}
}
если i>=k тогда i1++;
печатаем на экран (колво элементов удовлетворяющих условию задания равно i1 )
все.
на С++ думаю переведете (давно уже не пишу)
pankrat_mh, я бы предложил вариант с хэш-таблицами... Даже интересно сравнить, какой способ был бы быстрее.
по поводу хешей... напишите вариант,... хоть словами, мне будет интересно сравнить!
давно не пишу ничего, вот думаю постепенно вернуться в это дело, чтоб мозг не усох.
Если напишите, буду признателен! дадите еще повод мозг размять
давно не пишу ничего, вот думаю постепенно вернуться в это дело, чтоб мозг не усох.
Если напишите, буду признателен! дадите еще повод мозг размять
Меня терзают смутные сомненья на счёт полезности алгоритма с хешами для чисел. Для строк было бы самое то, особенно для длинных.
Структура данных — hash dictionary или hash set — в зависимости от ЯП. Суть алгоритма в том, чтобы проверять словарь, занесён ли уже ключ-число. Если да, то инкрементировать значение для ключа, если нет, то добавлять этот ключ со значением = 1. В итоге должно получиться множество всех чисел в виде ключей с количеством повторений в виде значений.
Структура данных — hash dictionary или hash set — в зависимости от ЯП. Суть алгоритма в том, чтобы проверять словарь, занесён ли уже ключ-число. Если да, то инкрементировать значение для ключа, если нет, то добавлять этот ключ со значением = 1. В итоге должно получиться множество всех чисел в виде ключей с количеством повторений в виде значений.
халявный метод
1. Создаешь массив с индексами от минимального до наибольшего значения
2. Прогоняешь по последовательности, плюсуя на единичку ячейки с индексами совпадающими со значениями последовательности
3. Потом считываешь количество единичек и сравниваешь с контрольным значением.
1. Создаешь массив с индексами от минимального до наибольшего значения
2. Прогоняешь по последовательности, плюсуя на единичку ячейки с индексами совпадающими со значениями последовательности
3. Потом считываешь количество единичек и сравниваешь с контрольным значением.
Цитата: LuckyD
халявный метод
1. Создаешь массив с индексами от минимального до наибольшего значения
2. Прогоняешь по последовательности, плюсуя на единичку ячейки с индексами совпадающими со значениями последовательности
3. Потом считываешь количество единичек и сравниваешь с контрольным значением.
1. Создаешь массив с индексами от минимального до наибольшего значения
2. Прогоняешь по последовательности, плюсуя на единичку ячейки с индексами совпадающими со значениями последовательности
3. Потом считываешь количество единичек и сравниваешь с контрольным значением.
Метод — говно. А если у меня в файле числа 1,2,3, 2, 1000000 мне что, создавать массив на миллион значений? Хотя, если бы были не кресты, а php или python, то можно было бы воспользоваться и им, но тогда это был бы не массив, а та же хеш таблица.