Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Помогите с задачкой. Не могу придумать алгоритм.

72K
16 марта 2013 года
MadWomaZ
1 / / 23.10.2011
Пусть последовательность является неубывающей. Определите количество элементов, которые появляются в этой последовательности более 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;
}
Какой алгоритм нужно сделать?
89K
16 марта 2013 года
pankrat_mh
3 / / 16.03.2013
алгоритм программы следующий.

переменные для работы программы
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 )
все.


на С++ думаю переведете (давно уже не пишу)
414
17 марта 2013 года
CassandraDied
763 / / 24.05.2012
pankrat_mh, я бы предложил вариант с хэш-таблицами... Даже интересно сравнить, какой способ был бы быстрее.
89K
19 марта 2013 года
pankrat_mh
3 / / 16.03.2013
по поводу хешей... напишите вариант,... хоть словами, мне будет интересно сравнить!
давно не пишу ничего, вот думаю постепенно вернуться в это дело, чтоб мозг не усох.
Если напишите, буду признателен! дадите еще повод мозг размять
414
19 марта 2013 года
CassandraDied
763 / / 24.05.2012
Меня терзают смутные сомненья на счёт полезности алгоритма с хешами для чисел. Для строк было бы самое то, особенно для длинных.
Структура данных — hash dictionary или hash set — в зависимости от ЯП. Суть алгоритма в том, чтобы проверять словарь, занесён ли уже ключ-число. Если да, то инкрементировать значение для ключа, если нет, то добавлять этот ключ со значением = 1. В итоге должно получиться множество всех чисел в виде ключей с количеством повторений в виде значений.
88K
24 марта 2013 года
LuckyD
2 / / 24.03.2013
халявный метод

1. Создаешь массив с индексами от минимального до наибольшего значения
2. Прогоняешь по последовательности, плюсуя на единичку ячейки с индексами совпадающими со значениями последовательности
3. Потом считываешь количество единичек и сравниваешь с контрольным значением.
414
24 марта 2013 года
CassandraDied
763 / / 24.05.2012
Цитата: LuckyD
халявный метод

1. Создаешь массив с индексами от минимального до наибольшего значения
2. Прогоняешь по последовательности, плюсуя на единичку ячейки с индексами совпадающими со значениями последовательности
3. Потом считываешь количество единичек и сравниваешь с контрольным значением.


Метод — говно. А если у меня в файле числа 1,2,3, 2, 1000000 мне что, создавать массив на миллион значений? Хотя, если бы были не кресты, а php или python, то можно было бы воспользоваться и им, но тогда это был бы не массив, а та же хеш таблица.

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог