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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
#1

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

15.06.2012, 12:31. Просмотров 2043. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2012, 12:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" (C++):

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

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

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

Установить, существуют ли в заданной последовательности чисел "близнецы" - C++
Дано натуральное число n. Установить, существуют ли среди чисел n, n + 1, ..., 2n близнецы, то есть простые числа, разница между...

Определить, есть ли в заданной последовательности хотя бы одна пара "соседних" нечётных чисел - C++
Дана последовательность натуральных чисел a1,a2, ..., a20. Определить, есть ли в последовательности хотя бы одна пара &quot;соседних&quot; нечетных...

Для последовательности целых, оканчивающейся "8", определить число чисел, больших первого введенного числа - C++
Помогите, пожалуйста, с заданием. Для последовательности целых чисел, оканчивающихся числом 8, определить количество чисел, больших...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:38  [ТС] #16
КонецСвета, да конечно)
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.06.2012, 11:53 #17
пробуйте:
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
#include <iostream>
#include <vector>
using namespace std;
typedef vector<double> MyVector;
MyVector vec;
 
int f(int a, int b, int t)
{
    if(b-a<2)
    {
        if(vec[a]==t)
            return a;
        if(vec[b]==t)
            return b;
        return -1;
    }
    int tmp=(b+a)/2;
    if(vec[tmp]>t)
        return f(a,tmp,t);
    else
        return f(tmp,b,t);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
 
    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, t, ind, j;
        int counter = 0;
        fscanf(pFile1, "%d", &n);
        fscanf(pFile1, "%d", &d);
        for (int i = 0; i <n; i++)
        {
            fscanf(pFile1, "%d", &x);
            vec.push_back(x);
        }
        for (int i = 0; i < vec.size()-1; i++)
        {   
            t=vec[i]+d;
            if(t>vec[n-1])
                break;
            ind=f(i+1,n-1, t);
            if(ind!=-1)
            {
                counter++;
                j=ind+1;
                while(j<n && vec[j]==t)
                {
                    j++; counter++;
                }
                j=ind-1;
                while(vec[j]==t)
                {
                    j--; counter++;
                }
            }
            
        }
        fprintf(pFile2, "%d", counter);
    }
    fclose(pFile1);
    fclose(pFile2);
    return 0;
}
1
dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 11:57 #18
vector не даст никакого убыстрения в данном случае, а алгоритм предложенный,если даже не хуже:
вместо цикла в цикле, делается два цикла в цикле
1
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:58  [ТС] #19
valeriikozlov, ОГРОМНОЕ СПАСИБО!)
0
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 12:22  [ТС] #20
dima koz, спасибо) уже сделали)
0
dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 12:42 #21
как, покажи

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

Определить количество положительных и отрицательных целых чисел в заданной последовательности - C++
с++. даны натуральное число n, действительные числа a1, .,an 1 Определить количество положительных и отрицательных целых чисел 2...

Постройте цепной список путем включения в него n целых чисел, идущих в неубывающей последовательности - C++
Постройте цепной список путем включения в него n целых чисел, идущих в неубывающей последовательности. В следующей части вашей программы ...

Записать в массив N целых чисел. Подсчитать количество пар противоположных чисел среди компонентов этого массива - C++
Записать в массив N целых чисел. Подсчитать количество пар противоположных чисел среди компонентов этого массива

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.06.2012, 22:08
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru