Форум программистов, компьютерный форум 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++ Создать список из целых чисел. После каждого элемента, равного "х" вставить элемент, равный "у"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,416
15.06.2012, 17:10     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #2
Смотри как можно:
1. Отсортировать всю последовательность
2. Сравниваем число со следующим:
2.1 Если текущее число + D меньше, то сравниваем со след. числом с последов.
2.2 Если равно, то счетчик++, сравниваем со след. числом.
2.3 Если число + D больше, то берем след. число.
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
15.06.2012, 17:46  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #3
Цитата Сообщение от MrGluck Посмотреть сообщение
Смотри как можно:
1. Отсортировать всю последовательность
2. Сравниваем число со следующим:
2.1 Если текущее число + D меньше, то сравниваем со след. числом с последов.
2.2 Если равно, то счетчик++, сравниваем со след. числом.
2.3 Если число + D больше, то берем след. число.
А можешь реализовать этот алгоритм? кстати последовательность уже отсортирована, вот полное задание: Задана неубывающая последовательность целых чисел. Найти количество пар чисел с заданной разностью D.
Ввод из файла INPUT.TXT. В первой строке задаются через пробел два целых числа: количество членов последовательности N и разность D (2 ≤ N ≤ 106, 1 ≤ D ≤ 106). Во второй строке вводятся через пробел N натуральных чисел последовательности A1 ≤ A2 ≤ ...≤ AN (Ai ≤ 109).
Вывод в файл OUTPUT.TXT. Вывести число пар (Ai, Aj) таких, что Ai – A j = D.
Ограничения. Время работы на одном тесте до 2 с. Объем используемой памяти до 1 Мгб.
Пример
Ввод
10 7
3 5 12 18 25 40 47 47 48 49
Вывод
4
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.06.2012, 05:23     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #4
MilitaNt, Вам поможет двоичный поиск.
C++ (Qt)
1
2
3
4
5
6
for (int i = 1; i < vec.size(); i++)
{
    t=vec[i]+d;
    // и вот с этого места ищите в диапазоне от i+1 до vec.size()-1 элемент со значением t
    // как только его нашли, то влево и вправо просматриваете и считаете общее количество элементов со значением t, увеличивая при этом значение  counter
}
Если значение d может быть отрицательным, то сразу после считывания этого значения умножаете его на -1 (результат все равно посчитает правильно).
Если значение d может быть равным 0, то можно сделать так:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = 1; i < vec.size(); i++)
{
    j=i+1;
    while(j<vec.size() &&  vec[i]==vec[j])
    {
        j++;
    }
    if(j>i+1)
    {
        t=j;
        while(t>i+1)
        {
            counter+=t-i+1;
            t--;
        }
        i=j-1;
    }
}
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 09:55  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #5
valeriikozlov, большое спасибо!
а не могли бы вы этот алгоритм полностью реализовать, d в диапазоне от 1 до 10^6
заранее спасибо!)
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 10:02     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #6
stdafx.h:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// stdafx.h: включаемый файл для стандартных системных включаемых файлов
// или включаемых файлов для конкретного проекта, которые часто используются, но
// не часто изменяются
//
 
#pragma once
 
#include "targetver.h"
 
#include <stdio.h>
#include <tchar.h>
 
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
 
#include <windows.h>
sequence.cpp:

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// sequence.cpp: определяет точку входа для консольного приложения.
//
//Ввод из файла INPUT.TXT.
//В первой строке задаются через пробел два целых числа: количество членов последовательности N и разность D (2 <= N <= 106, 1 <= D <= 106).
//Во второй строке вводятся через пробел N натуральных чисел последовательности A1 <= A2 <= ...<= AN (Ai <= 109).
 
// Вывод в файл OUTPUT.TXT. Вывести число пар (Ai, Aj) таких, что Ai – A j = D.
// Ограничения. Время работы на одном тесте до 2 с. Объем используемой памяти до 1 Мгб.
// Пример
// Ввод
// 10 7
// 3 5 12 18 25 40 47 47 48 49
// Вывод
// 4
 
#include "stdafx.h"
 
using namespace std;
 
void recordingOriginalFile(); //заполнение/запись исходного файла
int getRandomInt(unsigned short int,unsigned short int); //получение рандомного числа типа Int
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    //при  первом запуске программы, для программного создания файла для задания
    //при его наличии можно не использовать
    //написал, т.к. влом записывать файл вручную
    //recordingOriginalFile();
 
    //чтение 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);
    int *arr = new int [n];
    for (int i = 0; i < n; i++)
    {
            fscanf_s(pFile1, "%d", &arr[i]);
    }
    fclose(pFile1);
 
    //поиск пар
    int count = 0; // счетчик пар
    for (int i = 0; i < n; i++)
    {
 
        for (int j = 0; j<n ; j++)
        {
            if (arr[i] - arr[j] == d) 
                count ++;
 
        }
    }
    count /=2 ;
    int SecondTime = GetTickCount();
    cout << "count ="<< count <<endl;
    cout << "runtime this programm = "<< SecondTime - FirstTime << " ms (1 s = 1000 ms)"<<endl;
    _getch();
    return 0;
}
 
//функция записывает входной файл с  заданными параметрами по условиям задачи
//
void recordingOriginalFile()
{
    const int n = 106; //количество членов последовательности N
    const int d = 11;   //разность D
 
    int original [n], hold;
    //заполняем массив размера n рандомно числами от 2 до n
 
    srand((unsigned int)time(NULL));
    bool sorted;
    for (int i=0;i<n;i++)
    original[i] = getRandomInt(2,n);
    // сортируем 
    for (int j = 1; j < n; j++)
        {
        sorted = true;
        for (int k = 0; k < n - 1; k++)
            if (original[k] > original[k + 1])
            {
                hold = original[k];
                original[k] = original[k + 1];
                original[k + 1] = hold;
                sorted = false;
            }
        if (sorted) 
            break;
        }   
 
    //записываем
    FILE *pFileOriginalRecording;
 
    fopen_s(&pFileOriginalRecording,"d:\\test\\input.txt", "w");
    fprintf(pFileOriginalRecording,"%d ",n);
    fprintf(pFileOriginalRecording,"%d ",d);
    fprintf(pFileOriginalRecording,"%c",char(10));
 
    for (int i = 0; i < n; i++)
    {
        fprintf(pFileOriginalRecording,"%d ",original[i]);
    }
    fclose(pFileOriginalRecording);
}
 
int getRandomInt(unsigned short int initialValue,unsigned short int finalValue)
{
    
    return  (initialValue + rand() % (finalValue-initialValue+1));
}
время выполнения несколько мс при N = 106, занимает в памяти не больше 700 кб

запись счетчика пар, думаю, сможешь самостоятельно сделать, по образцу в recordingOriginalFile()
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 10:20  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #7
dima koz, а для чего сортировка? последовательность по заданию вроде как неубывающая => отсортирована, или я не прав?
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 10:26     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #8
Цитата Сообщение от MilitaNt Посмотреть сообщение
dima koz, а для чего сортировка? последовательность по заданию вроде как неубывающая => отсортирована, или я не прав?
прав, они не нужны.
эти две функции(генерируют исходный файл для задания - input.txt) после мэйна я сделал только для того,чтобы ручками самому не создавать файл, ведь ты его к заданию не прикладывал, а у меня его нет.

+ не забудь сделать запись счетчика в output.txt
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 10:31  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #9
dima koz а можешь проверить как долго твоя программа будет работать на тесте с последовательностью в 100000 элементов?
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 10:43     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #10
Цитата Сообщение от MilitaNt Посмотреть сообщение
dima koz а можешь проверить как долго твоя программа будет работать на тесте с последовательностью в 100000 элементов?
Если предоставишь файл input.txt с последовательностью в 100000 элементов, то почему нет
а так самому его долго генерировать, сортировка выбрана самая медленная и простая

но N = 100000 противоречит условию твоего же собственного задания :
Цитата Сообщение от MilitaNt Посмотреть сообщение
количество членов последовательности N и разность D (2 ≤ N ≤ 106, 1 ≤ D ≤ 106).

проверил, при N=100001
ms - 12730
KБ - 1036
тестовый файл с последовательностью(input.txt) получился 554 КБ
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 10:52  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #11
dima koz, ))) там было 10^6, ^ я обозначил степень)))) я уже протестировал) на такой последовательности работает 22 секунды...а нужно не более 2(((((
еще предложили двоичный поиск, но я не знаю как его реализовать
C++
1
2
3
4
5
6
for (int i = 1; i < vec.size(); i++)
{
    t=vec[i]+d;
    // и вот с этого места ищите в диапазоне от i+1 до vec.size()-1 элемент со значением t
    // как только его нашли, то влево и вправо просматриваете и считаете общее количество элементов со значением t, увеличивая при этом значение  counter
}
Добавлено через 3 минуты
dima koz, вот генератор теста)
C++
1
2
3
4
5
6
7
int _tmain(int argc, _TCHAR* argv[])
{
    FILE *pFile2 = fopen("output.txt", "w");
    for (int i = 1; i <= 100000; i++)
        fprintf(pFile2, "%d ", i);
    return 0;
}
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 10:56     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #12
Цитата Сообщение от MilitaNt Посмотреть сообщение
dima koz, ))) там было 10^6, ^ я обозначил степень)))) я уже протестировал) на такой последовательности работает 22 секунды...а нужно не более 2(((((
еще предложили двоичный поиск, но я не знаю как его реализовать
при N = 10 ^6 нужен совершенно другой алгоритм поиска пар,чтобы уложиться за 2 секунды.
если найдешь такой алгоритм, возможно, помогу реализовать

Цитата Сообщение от MilitaNt Посмотреть сообщение
dima kozвот генератор теста)
у меня уже готовый файлик
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:00  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #13
dima koz, так вот я и сам не знаю какой алгоритм нужен, ну вот я выше показал двоичный поиск, он ускорит работу?
C++
1
2
3
4
5
6
for (int i = 1; i < vec.size(); i++)
{
    t=vec[i]+d;
    // и вот с этого места ищите в диапазоне от i+1 до vec.size()-1 элемент со значением t
    // как только его нашли, то влево и вправо просматриваете и считаете общее количество элементов со значением t, увеличивая при этом значение  counter
}
Добавлено через 3 минуты
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.06.2012, 11:20     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #14
Цитата Сообщение от MilitaNt Посмотреть сообщение
а не могли бы вы этот алгоритм полностью реализовать, d в диапазоне от 1 до 10^6
мог бы, но ответьте на несколько вопросов:
- какой нужен язык программы (Вы пишите на С++ в разделе Паскаля)?
- максимальное количество элементов массива?
- значения элементов массива в каком диапазоне?
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:27  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #15
можно и на паскале и на с++, дело в том, что изначально я не видел что пишу на форуме паскаля)))
2 <= n <= 10^6 , 1 <= d <= 10^6
значения любые, но с условием что последовательность неубывающая (поэтому думаю сортировка уже не нужна)
вот простой генератор теста для данной задачи
C++
1
2
3
4
5
6
7
int _tmain(int argc, _TCHAR* argv[])
{
    FILE *pFile2 = fopen("output.txt", "w");
    for (int i = 1; i <= 100000; i++)
        fprintf(pFile2, "%d ", i);
    return 0;
}
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:38  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #16
КонецСвета, да конечно)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.06.2012, 11:53     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #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;
}
dima koz
 Аватар для dima koz
23 / 17 / 1
Регистрация: 05.06.2012
Сообщений: 72
Записей в блоге: 5
16.06.2012, 11:57     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #18
vector не даст никакого убыстрения в данном случае, а алгоритм предложенный,если даже не хуже:
вместо цикла в цикле, делается два цикла в цикле
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:58  [ТС]     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" #19
valeriikozlov, ОГРОМНОЕ СПАСИБО!)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.06.2012, 12:22     В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D"
Еще ссылки по теме:

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

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

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

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