Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
15.06.2012, 12:31     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #1
Помогите пожалуйста оптимизировать алгоритм, тут приведен простой перебор и на большом тесте программа работает очень долго. По заданию время работы программы должно не превышать 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2012, 12:31     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D"
Посмотрите здесь:

C++ Дан массив из 9 целых чисел. Найти сумму элементов массива и, если она четная, вывести сообщение "Сумма четная", в противном случае напечатать "Сумма
Записать в массив N целых чисел. Подсчитать количество пар противоположных чисел среди компонентов этого массива C++
C++ Постройте цепной список путем включения в него n целых чисел, идущих в неубывающей последовательности
Найти количество двух- и количество трехразрядных чисел в заданной последовательности C++
C++ Создать список из целых чисел. После каждого элемента, равного "х" вставить элемент, равный "у"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 12:42     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #21
как, покажи

Добавлено через 12 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
ind=f(i+1,n-1, t);
а что такое f ? в коде не нашел.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.06.2012, 07:29     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #22
Цитата Сообщение от dima koz Посмотреть сообщение
а что такое f ? в коде не нашел.
это функция. См строку 7 кода.
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
17.06.2012, 09:30     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #23
Цитата Сообщение от valeriikozlov Посмотреть сообщение
это функция. См строку 7 кода.
Да,спс, надо было мне не флудить, а поискать по-лучше(нашел через минуту после своего вопроса).
Я раньше всегда был уверен, что циклы эффективнее(быстрее и экономнее) рекурсии, практика обычно так показывала, а тут наоборот,я в шоке...
Почему так в нашем случае получилось?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.06.2012, 10:59     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #24
Цитата Сообщение от dima koz Посмотреть сообщение
Почему так в нашем случае получилось?
погуглите бинарный поиск.
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
17.06.2012, 12:01  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #25
valeriikozlov, привет!
к сожалению, на большом тесте она снова очень долго работала(на максимальном тесте), к ней появился еще один алгоритм, можешь помочь мне реализовать его?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.06.2012, 12:43     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #26
Цитата Сообщение от MilitaNt Посмотреть сообщение
к ней появился еще один алгоритм,
что еще за алгоритм?
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
17.06.2012, 12:45  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #27
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
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.06.2012, 13:08     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #28
попозже напишу здесь код (когда освобожусь).
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
17.06.2012, 14:00     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #29
Цитата Сообщение от 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;
    }
  }
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
17.06.2012, 22:08  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #30
valeriikozlov, добрый вечер! еще не сделали?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2012, 20:24     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D"
Еще ссылки по теме:

Дана последовательность из n целых чисел. Найти количество нечетных элементов этой последовательности C++
Для последовательности целых, оканчивающейся "8", определить кол-во чисел, больших первого введенного числа C++
C++ В последовательности целых чисел определить количество чётных чисел кратных 7

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

Или воспользуйтесь поиском по форуму:
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
19.06.2012, 20:24  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #31
valeriikozlov, хм
Yandex
Объявления
19.06.2012, 20:24     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D"
Ответ Создать тему
Опции темы

Текущее время: 21:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru