С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.91/22: Рейтинг темы: голосов - 22, средняя оценка - 4.91
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21

В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D"

15.06.2012, 12:31. Показов 5046. Ответов 30
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите пожалуйста оптимизировать алгоритм, тут приведен простой перебор и на большом тесте программа работает очень долго. По заданию время работы программы должно не превышать 2 секунд.
Заранее большое спасибо!
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int _tmain(int argc, _TCHAR* argv[])
{
    typedef vector<double> MyVector;
    MyVector vec;
    FILE *pFile1 = fopen("input.txt", "r");
    FILE *pFile2 = fopen("output.txt", "w");
    int ch;
    if (!pFile1)
    {
        printf("File opening error\n");
        return 1;
    }
    else
    {
        int n, d, x, support, diff;
        int counter = 0;
        fscanf(pFile1, "%d", &n);
        fscanf(pFile1, "%d", &d);
        for (int i = 1; i <= n; i++)
        {
            fscanf(pFile1, "%d", &x);
            vec.push_back(x);
        }
        for (int i = 1; i < vec.size(); i++)
        {   
            support = i;
            while (support >= 0)
            {
                diff = vec[i] - vec[support];
                if (diff == d)
                {
                    counter++;
                }
                support = support - 1;
            }
        }
        fprintf(pFile2, "%d", counter);
    }
    fclose(pFile1);
    fclose(pFile2);
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
15.06.2012, 12:31
Ответы с готовыми решениями:

В заданной последовательности целых чисел найти количество чисел кратных заданному
Напишите программу, которая в последовательности целых чисел определяет количество чисел, кратных 5 или 7. Программа получает на вход целые...

Определить в заданной последовательности целых чисел количество чисел Фибоначчи
Выполнить задания, если задана последовательность целых чисел длиной n. Определить в заданной последовательности целых чисел количество...

Определить в заданной последовательности целых чисел количество чисел Фибоначчи
Определить в заданной последовательности целых чисел количество чисел Фибоначчи.

30
 Аватар для dima koz
23 / 17 / 7
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 12:42
Студворк — интернет-сервис помощи студентам
как, покажи

Добавлено через 12 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
ind=f(i+1,n-1, t);
а что такое f ? в коде не нашел.
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
17.06.2012, 07:29
Цитата Сообщение от dima koz Посмотреть сообщение
а что такое f ? в коде не нашел.
это функция. См строку 7 кода.
0
 Аватар для dima koz
23 / 17 / 7
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
17.06.2012, 09:30
Цитата Сообщение от valeriikozlov Посмотреть сообщение
это функция. См строку 7 кода.
Да,спс, надо было мне не флудить, а поискать по-лучше(нашел через минуту после своего вопроса).
Я раньше всегда был уверен, что циклы эффективнее(быстрее и экономнее) рекурсии, практика обычно так показывала, а тут наоборот,я в шоке...
Почему так в нашем случае получилось?
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
17.06.2012, 10:59
Цитата Сообщение от dima koz Посмотреть сообщение
Почему так в нашем случае получилось?
погуглите бинарный поиск.
2
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
17.06.2012, 12:01  [ТС]
valeriikozlov, привет!
к сожалению, на большом тесте она снова очень долго работала(на максимальном тесте), к ней появился еще один алгоритм, можешь помочь мне реализовать его?
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
17.06.2012, 12:43
Цитата Сообщение от MilitaNt Посмотреть сообщение
к ней появился еще один алгоритм,
что еще за алгоритм?
1
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
17.06.2012, 12:45  [ТС]
valeriikozlov, 1. Объявить два файла f1 и f2 на чтение, связав оба с INPUT.TXT.
2. Начать чтение из f2 раньше, т.е. порядковый номер числа у f2 должен быть больше.
3. Пока разность прочитанных значений f2 и f1 больше d, читаем из f1.

4. Аналогично пока разность прочитанных значений f2 и f1 меньше d, читаем из f2.
5. Как только разность равна d, обрабатываем ситуацию.
1) Продвигаясь по f1, считаем, сколько раз повторяется одно и то же значение. Пусть s раз.
2) Продвигаясь по f2, считаем, сколько раз повторяется одно и то же значение. Пусть t раз.
3) Добавляем количество пар s*t.


можешь код отправить потом мне на почтовый ящик? sergey_pushkin_00@mail.ru
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
17.06.2012, 13:08
попозже напишу здесь код (когда освобожусь).
0
 Аватар для dima koz
23 / 17 / 7
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
17.06.2012, 14:00
Цитата Сообщение от valeriikozlov Посмотреть сообщение
погуглите бинарный поиск.
спасибо.
вкурил, название у поиска запутывающее

можно попросить сказать какие недочеты есть ?
поиск сделал без рекурсии :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(0,"Russian");
 
    //чтение input.txt
    //заполнение переменных заданными значениями
    int n,d;
 
    int FirstTime = GetTickCount();
    
    FILE *pFile1;
    fopen_s(&pFile1,"d:\\test\\input.txt", "r");
    fscanf_s(pFile1, "%d", &n);
    fscanf_s(pFile1, "%d", &d);
    unsigned int *arr = new unsigned int [n];
    
    for (int i = 0; i < n; i++)
    {
            fscanf_s(pFile1, "%d", &arr[i]);
    }
    fclose(pFile1);
    unsigned int t;
    //поиск пар
    int count = 0; // счетчик пар
 
    for (int i = 0; i < n; i++)
    {
        if (i> 0 && arr[i]==arr[i-1])
            continue;
 
        t=arr[i]+d;
 
        int found = BinarySearch (arr, i, n, t);
        if (found !=-1)
        {
            count++;
            int up = 1;
            while (arr[found + up] == t)
            {
                up++;
                count++;
            }
            int down = 1;
            while (arr[found - down] == t)
            {
                down++;
                count++;
            }
        }
        
 
        
    }
 
    int SecondTime = GetTickCount();
    cout << "count ="<< count <<endl;
    cout << "runtime this programm in binary search= "<< SecondTime - FirstTime << " ms (1 s = 1000 ms)"<<endl;
 
    _getch();
    return 0;
}
 
 
int BinarySearch (unsigned int arr[], int lb, int ub, unsigned int key)
  {
    int m;
 
    while(true)
    {
    m = (lb + ub)/2;
    if (key < arr[m]) 
    {
      ub = m - 1;
    }
    else if (key > arr[m]) 
    {
      lb = m + 1;
    }
    else
      return m;
    if (lb > ub) 
    return -1;
    }
  }
0
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
17.06.2012, 22:08  [ТС]
valeriikozlov, добрый вечер! еще не сделали?
0
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
19.06.2012, 20:24  [ТС]
valeriikozlov, хм
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
19.06.2012, 20:24
Помогаю со студенческими работами здесь

Определить в заданной последовательности целых чисел количество чисел Фибоначчи
Определить в заданной последовательности целых чисел количество чисел Фибоначчи.

Найти количество чисел, равных между собой, в неубывающей последовательности
Помогите пожалуйста Дана непустая последовательность вещественных чисел, оканчивающаяся числом 1000. Последовательность является...

В заданной конечной последовательности целых чисел найти количество элементов кратных 7 (MASM32)
В заданной конечной последовательности целых чисел найти количество элементов кратных 7 (MASM32)

В последовательности целых чисел найти количество чисел в которых нет 3 и 7 и наименьшее среди этих чисел
Разработать процедуру, которая в последовательности целых чисел находит количество чисел в которых нет 3-ки и 7-ки и наименьшее среди этих...

Дан массив целых чисел, который задает цвет каждой из носков, найти количество пар одинаковых чисел
Роман работает в магазине одежды и должен рассортировать огромную кучу носков по цветам, чтобы продать их. Дан массив целых чисел,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
31
Ответ Создать тему
Новые блоги и статьи
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru