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

Найти самую длинную возрастающую цепочку простых чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
ZeonExpert
0 / 0 / 0
Регистрация: 20.12.2010
Сообщений: 21
13.09.2011, 10:55     Найти самую длинную возрастающую цепочку простых чисел #1
Привет всем
Решаю задачку:

Найти самую длинную возрастающую цепочку простых чисел
В заданном бинарном файле необходимо найти самую длинную возрастающую
цепочку простых чисел. Бинарный файл трактуется как последовательность 6-ти
байтовых беззнаковых целых. Размер файла может быть любым, если размер файла не
кратен 6, то лишние байты с конца файла игнорируются. Элементы цепочки не обязаны
идти друг за другом в файле, между элементами цепочки могут встречаться не простые
числа в любом количестве. Из двух цепочек одинаковой длины предпочтение отдается
той, у которой первый элемент больше. Если длины и первые элементы цепочек
совпадают, предпочтение отдается той, у которой смещение первого элемента меньше.

Задача должна быть реализована в виде консольного приложения для Windows
32bit и должна быть выполнена на языке C++. Файл с данными указывается как параметр
командной строке. Реализация должна быть многопоточной, хочется иметь бонус от
запуска приложения на многопроцессорных (Core2Quad) системах. Отдельный плюс,
если во время выполнения будет отображаться прогресс обработки файла.
Результатом работы должен быть вывод первого элемента цепочки и его смещения,
последнего элемента цепочки и его смещенья и длины цепочки, или, если цепочка не
была найдета – сообщение об этом прискорбном факте.

Примеры формата файла:

Содержание файла (byte, hex, 34 байта)
01 00 00 00 00 00 02 00
00 00 00 00 03 00 00 00
00 00 00 00 00 00 00 80
00 00 00 00 80 00 FF FF
FF FF

Числа в файле
1, 2, 3, 140737488355328, 549755813888


Примеры последовательностей и найденные цепочки:
Последовательность
2, 3, 5, 3, 5, 7, 11
2, 3, 4, 5, 6, 7, 3, 5, 7
2, 3, 10,5, 6, 7, 3, 5, 7
2, 3, 3, 5, 6, 7, 3, 5, 7
2, 3, 5, 3, 5, 11
2, 3, 5, 2, 5, 11


Найденная цепочка
3, 5, 7, 11
2, 3, 5, 7
2, 3, 5, 7
3, 5, 7
3, 5, 11
2, 3, 5

Может кто-нить уже сталкивался с подобным сабжем, заранее спасибо за комменты?

Добавлено через 13 часов 3 минуты
Если есть идеи пишите
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.09.2011, 10:55     Найти самую длинную возрастающую цепочку простых чисел
Посмотрите здесь:

найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
C++ В массиве целых чисел найти максимально длинную возрастающую последовательность
Цикл: Найти самую длинную неубывающую цепочку чисел C++
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
13.09.2011, 13:31     Найти самую длинную возрастающую цепочку простых чисел #2
Не встречалось. Между прочим задачка интересная.

Идеи такие:
*. разбить на подзадачи, реализовать каждую отдельно, сложить вместе и получить профит.

1. определиться с алгоритмом определения простоты. Насколько я понимаю нам необходимо гарантировано знать, является ли заданное число простым. Без поиска по литературе мне известно два алгоритма: акс и перебором. Где-то читал, что для определения простоты числа перебор является одним из оптимальных алгоритмов для чисел меньших 2^20 (без пруфлинка). Пусть это будет функция is_simple();
2. Поскольку большинство вычислений будут проходить в is_simple(), именно её выделять в отдельную нить.
3. Пишем под вин, сия ОСЬ вроде бы умеет автоматически разбрасывать нити по процессорам с оптимальным распределением нагрузки, так что с этим можно не заморачиваться.
4. Реализуем чтение чисел из фаила, передачу оных в нити, хранение выделенных последовательностей, контроль работы ниток.

для начала как-то так.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
15.09.2011, 14:20     Найти самую длинную возрастающую цепочку простых чисел #3
Ниже: трэд, нить, поток - синонимы, мэйн-трэд - основной поток процесса.
Касательно собственно вычислений. Старался комментировать подробно. Общий принцип: считать последовательность в массив, выделить простые. После этого можно выделять возрастающие подпоследовательности и искать наидлиннейшую или еще каким либо образом с ними работать. Заголовочник simple.h содержит объявление функции определения простоты числа, например
такой
C++
1
2
3
4
5
6
int is_simple(long long int arg){
    if( (arg == 1)||(arg == 2)) return 0; //если мы не хотим чтобы 1 и 2 попадали в список наших простых чисел.
    for(long long int i = 2; i*i <=arg; i +=2 )
        if( arg%i == 0) return 0;   
    return 1;       
}
.
Код является примером работы с потоками RTL и не более того. Чуть позже напишу несколько соображений касательно того как такая задача должна решаться. Каждый поток выполняет расчеты для k+th члена последовательности (где k = 1,2,3... и т.д, а th - номер потока), то есть 3-й поток из 8 проверит 3,11,19 и т.д. члены. При порождении трэда ему нужно передать значение th, поскольку это действие выполняется передачей указателя на переменную( которая выступает итератором в порождающем трэде) то, происходят "финты ушами" - помещение значения итератора в массив и передача указателя на элемент массива (то есть каждому порождённому трэду будет соответсвовать свой элемент массива).Это не совсем красиво, но остальные варианты очень громоздки. Ну и последнее замечание: тема для меня новая, возможно что-либо можно сделать более оптимально/рационально/просто.
пример.
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
#include<iostream>
#include<fstream>
#include<vector>
#include<utility>
#include<cassert>
#include<process.h>
#include<windows.h>
#include"simple.h"
 
// #define USE_MULTI_THREAD 1
 
using namespace std; 
 
//Закинем числа в массив (глобальный, дабы доступ был у всех потоков).
//где целые - наши числа, а булевы - результат проверки на простоту
vector< pair<long long int,bool> >numbers;
const int count = 4;    //количество порождаемых трэдов.
#ifdef USE_MULTI_THREAD
    //завершённый трэд будет генерировать событие (Events).
    //поскольку трэдов будет несколько, используем табличку:
    HANDLE th_events_table[count]; //для упрощения доступа делаем глобальной.
#endif
 
 
void myThread(void* ptr);
int main(int argn, char* argv[]){
    //входной фаил в качестве параметра, например C:> a.exe input.bin
    assert (argn == 2);
    char* filename = argv[1];
 
    //поскольку разбираем многопоточность, пусть числа 
    //пока лежат в тхт фаиле (строка = число);
    //вытаскиваем их из фаила:
    ifstream in;
    in.open(filename,fstream::in);
        while(in.good()){
            pair<long long int,bool>x;
            in>>x.first;
            x.second = false;
            numbers.push_back(x);
        }
    in.close();
    
    //числа в массиве. Проверяем на простоту каждое число:
#ifndef USE_MULTI_THREAD
    //однопоточный вариант:
    for(int i = 0;i <numbers.size(); ++i)
        numbers[i].second = (bool)is_simple(numbers[i].first);
#endif
#ifdef USE_MULTI_THREAD
//многопоточный вариант:
    //Изначально события должны быть в свободном состоянии
    for(int i = 0; i < count; ++i)
        th_events_table[i] = CreateEvent(NULL,false,false,NULL);
    
    //порождаем трэды:
    int arr[count]; //свой итератор, для каждого треда. не под "дзену", зато просто.
    for(int i = 0; i < count; ++i){
        arr[i] = i;
        assert( _beginthread(myThread, 0, &arr[i]) );
    }
    //Вобще говоря, main-трэд ни чуть не хуже всех остальных
    //и тоже вполне себе может принимать участие в вычислениях,
    //однако для наглядности он будет просто ожидать окончания
    //порождённых.
    
    //ожидаем завершения всех запущеных тредов:
    WaitForMultipleObjects(count,th_events_table,true,INFINITE);
    
    
    for(int i = 0; i < count; ++i)
        assert( CloseHandle(th_events_table[i]) );
#endif
    
    //Теперь выводим только простые:
    for(int i = 0;i <numbers.size(); ++i)
        if( numbers[i].second ) cout<<numbers[i].first<<endl;
    
return 0;   
}
 
#ifdef USE_MULTI_THREAD
void myThread(void* ptr){
    int thred_arg = *(int*)ptr; //начальная позиция в векторе чисел 
                                //и номер в массиве событий..
    //две строки ниже - демонстрационные и не нужны:
    Sleep(1000*thred_arg);
    cout<<"thread "<<thred_arg<<endl;
    
    //собственно вычисление простоты:
    for(int i = thred_arg; i < numbers.size(); i += count)
        numbers[i].second = is_simple(numbers[i].first);
    
    //вычисление завершены. Генерируем событие:
    SetEvent(th_events_table[thred_arg]);
    _endthread();
}
#endif
ZeonExpert
0 / 0 / 0
Регистрация: 20.12.2010
Сообщений: 21
15.09.2011, 14:31  [ТС]     Найти самую длинную возрастающую цепочку простых чисел #4
Спасибо Vladimir.

Я пробовал сделать, пока точно так не получается:
Примерно последовательность такая:
1. Считываем в поток ввода бинарный файл из argv[..]
2. Записываем его в vector<UINT8> (где typedef unsigned long int UINT8)
3. Начинаю анализировать перебором в сравнении что следующий элемент больше текущего
4. Далее выделяю это в отдельный массив векторов.
5. Вот тут дальше вопрос как определять что число простое и что можно поместить в отдельные нити расчитывать
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.09.2011, 16:06     Найти самую длинную возрастающую цепочку простых чисел #5
Цитата Сообщение от ZeonExpert Посмотреть сообщение
2, 3, 4, 5, 6, 7, 3, 5, 7
2, 3, 10,5, 6, 7, 3, 5, 7
Но здесь не цепочка, у вас закрашенные элементы расположены непоследовательно.
А задача простая в общем-то...
Решается динамикой кстати.

Добавлено через 15 минут
Для подпоследовательности(не цепочки, для цепочки нужно подправить пару строк) как-то так получится.
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
#include <iostream>
 
int main()
{   
    const int MAX_VALUE = 100500; //максимально возможная цифра
 
    char sieve[ MAX_VALUE ] = { 1, 1 }; //решето Эратосфена
    
    //заполнение решета
    
    for (int i = 2; i < MAX_VALUE ; ++i)
    {
        
        if ( sieve[i] == 0 )
        {
            for ( int j = i * 2 ; j < MAX_VALUE ; j += i )
                sieve[j] = 1;
        }
    }
    
    int arr[] = { 2, 3, 10,5, 6, 7, 3, 5, 7 };
    int size = sizeof( arr ) / sizeof( *arr );
    
    int * dinamic = new int [ size ];
    
    /* 
     * Для каждого члена последовательности находим длину максимальной
     * подпоследовательности, заканчивающейся на этом элементе
     */
    
    dinamic[0] = 0;
    for (int i = 1; i < size ; ++i)
    {
        dinamic[0] = 0;
        
        //если число не простое, последовательность не может оканчиваться на этот элемент
        if ( sieve[ arr[i] ] != 0 )
            continue;
        
        for ( int j = i - 1; j >= 0 ; --j)
            if ( sieve[arr[j]] == 0 && arr[j] < arr[i] )
                dinamic[i] = std::max( dinamic[i], dinamic[j] + 1 );
    }
    
    /*
     * нахождение длины максимальной подпоследовательности и элемента, 
     * на котором она заканчивается
     */
     
    int max = 0, pos = 0;
    for (int i = 0; i < size ; ++i)
    if ( dinamic[i] > max )
    {
        max = dinamic[i];
        pos = i;
    }
    
    //заполнение массива с ответом
    int * answer = new int [ dinamic[pos] + 1];
    
    answer[0] = arr[pos];
    int end = 0;
    
    for (int i = pos - 1, x = pos; i >= 0; --i)
    {
        if ( dinamic[i] + 1 == dinamic[x] )
        { 
            answer[++end] = arr[i];
            x = i;
        }
    }
    
    
    for (int i = end; i >= 0 ; --i)
        std::cout << answer[i] << ' ';
    
    delete[] answer;    
    delete[] dinamic;
}
За O(nlogn) примерно находит.

Для цепочки еще проще
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
/*
 * Найти максимальную по длине возрастающую цепочку простых чисел
 */
 
#include <iostream>
 
int main()
{   
    const int MAX_VALUE = 100500; //максимально возможная цифра
 
    char sieve[ MAX_VALUE ] = { 1, 1 }; //решето Эратосфена
    
    //заполнение решета
    
    for (int i = 2; i < MAX_VALUE ; ++i)
    {
        
        if ( sieve[i] == 0 )
        {
            for ( int j = i * 2 ; j < MAX_VALUE ; j += i )
                sieve[j] = 1;
        }
    }
    
    int arr[] = { 2, 3, 3, 5, 6, 7, 3, 5, 7  };
    int size = sizeof( arr ) / sizeof( *arr );
    
    int * dinamic = new int [ size ];
    
    /* 
     * Для каждого члена последовательности находим длину максимальной
     * подпоследовательности, заканчивающейся на этом элементе
     */
    
    dinamic[0] = 0;
    for (int i = 1; i < size ; ++i)
    {
        dinamic[0] = 0;
        
        //если число не простое, последовательность не может оканчиваться на этот элемент
        if ( sieve[ arr[i] ] != 0 )
            continue;
        
        if ( sieve[ arr[i - 1] ] == 0 && arr[i - 1] < arr[i] )
            dinamic[i] = std::max( dinamic[i], dinamic[i - 1] + 1 );
    }
    
    /*
     * нахождение длины максимальной подпоследовательности и элемента, 
     * на котором она заканчивается
     */
     
    int max = 0, pos = 0;
    for (int i = 0; i < size ; ++i)
    if ( dinamic[i] > max )
    {
        max = dinamic[i];
        pos = i;
    }
    
    //заполнение массива с ответом
    for (int i = pos - dinamic[pos] ; i <= pos ; ++i)
        std::cout << arr[i] << ' '; 
    
    delete[] dinamic;
}
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
15.09.2011, 16:14     Найти самую длинную возрастающую цепочку простых чисел #6
в продолжение моего поста:
Смысл распараллеливания вычислений на нескольких процессорах в первую очередь в получении выгоды по времени.
первое: в приведённом выше примере данные сначала считываются а потом обрабатываются. Значит, если время чтения 50 секунд, и время вычислений 50 секунд, то распределив вычисления по 4 потокам в результате имеем 40% профита ( 50+50/4 = 62 секунды вместо 100 секунд в случае однопоточных вычислений.)
второе:, если одному из потоков попадётся набор больших и, следовательно, сложных для проверки чисел, то остальные потоки справившись со своими задачами будут вынуждены ждать "неудачника". Что еще уменьшит профит (причем уменьшать будет довольно быстро)
третье: то, чего не делали - нужно еще найти наибольшую подпоследовательность, что тоже потребует времени.
четвертое: выбран не самый удачный тест простоты.

первые три пункта исправляются так:
в начале программы создаётся нужное количество вычислительных потоков (далее пул), они переводятся в режим ожидания, так же создаётся поток для чтения данных из фаила и поток для поиска наибольшей подпоследовательности который тоже ждёт своего часа. Поток ввода работает с двумя буферами. Сначала данные из фаила помещаются в буфер1, буфер1 отправляется пулу (вернее пул получает разрешение работать с буфером). Поток ввода не останавливаясь заполняет буфер2. Когда буфер2 заполнен, ввод приостанавливается. В это время пул потоков обрабатывает буфер1 : Каждый вычислительный поток берёт число из буфера, выполняет для него тест простоты и отправляет результат потоку поиска, после чего берёт новое число из буфера. И так пока буфер не опустеет. После того как пул обработает весь буфер, потоки переводятся в режим ожидания.
Если буфер2 полон, а буфер1 пуст - они меняются местами, поток ввода снова начинает считывать данные из фаила, а пул обрабатывать числа из полного буфера.
А параллельно этому всему работает поток поиска, выявляя в переданных ему пулом данных максимальную подпоследовательность.
После окончания фаила и завершения вычислений во всех потоках, происходит вывод результата, освобождение ресурсов и т.п.
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2011, 16:36     Найти самую длинную возрастающую цепочку простых чисел #7
5. Вот тут дальше вопрос как определять что число простое и что можно поместить в отдельные нити расчитывать
В каждой нити выполняется функция,которая берёт параметр - указатель на начало числа в файле (то есть у каждого треда будет указатель со своим смещением относительно начала файла).
Эта функция проверяет число на простоту плюс можно класть число в структуру с флагом. Как проверять - Vladimir в принципе всё расписал. Потом все нити объединяются, и проходимся по структурам,считая последовательности. Размер последовательности можно хранить прямо в структуре числа, а также его смещение в файле. Например:
C++
1
2
3
4
5
6
struct number {
   unsigned long  original_number; // тут нужно правильный тип вписать)
   bool           is_simple;
   int            index_in_sequence;
   int            shift;
}
index_in_sequence содержит текущий индекс в последовательности, если обнаруживаем признаки начала новой последовательности, то меняем index_in_sequence снова на 0. Проходим в цикле по всем структурам и сохраняем указатель на структуру с наибольшим index_in_sequence. И потом остаётся только напечатать числа и их смещения.
Сразу в цикле можно создать максимально возможный блок тредов или меньше, в зависимости от размера файла.(например, у меня на 32-битной системе было ограничение в примерно 280-300 тредов) . На 64-битной системе ограничение гораздо больше (несколько десятков тысяч,точно не знаю). Если файл больше чем (блок тредов)*(размер числа), то создаём блоки нитей пачками, пока не достигнем конца файла.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
15.09.2011, 16:43     Найти самую длинную возрастающую цепочку простых чисел #8
Цитата Сообщение от ZeonExpert Посмотреть сообщение
Спасибо Vladimir.

Я пробовал сделать, пока точно так не получается:
Примерно последовательность такая:
1. Считываем в поток ввода бинарный файл из argv[..]
2. Записываем его в vector<UINT8> (где typedef unsigned long int UINT8)
3. Начинаю анализировать перебором в сравнении что следующий элемент больше текущего
4. Далее выделяю это в отдельный массив векторов.
5. Вот тут дальше вопрос как определять что число простое и что можно поместить в отдельные нити расчитывать
гмм.. (посмотрите внимательно пример еще раз, там уже реализована многопоточность и обработка простых чисел. снимите комментарий перед define в восемнадцатой строке )

1 и 2 смущает, можно функции посмотреть??
3 и 4: 12 13 14 15 16 3 17 18 - здесь одна подпоследовательность 13 17, у вас она окажется в разных массивах, вы учли такой вариант??
5. методы определения простоты числа есть на вики хотя бы...

diagon, вы хотябы задание читали перед ответом.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2011, 16:49     Найти самую длинную возрастающую цепочку простых чисел
Еще ссылки по теме:

Найти в матрице самую длинную цепочку подряд стоящих 0 по горизонтали или вертикали C++
C++ Удалить самую длинную цепочку четных элементов
Найти самую длинную последовательность простых чисел C++

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.09.2011, 16:49     Найти самую длинную возрастающую цепочку простых чисел #9
Цитата Сообщение от Vladimir. Посмотреть сообщение
diagon, вы хотябы задание читали перед ответом.
Сейчас прочитал, мой алгоритм с подпоследовательностью все равно подходит, только нужно учесть первый элемент и смещение( ну и еще пачку подробностей вроде отсутствия простых чисел, но мне лень это все реализовывать, я просто алгоритм показал).
А по условию не подходит этот пример
2, 3, 5, 3, 5, 7, 11
там двойка красным не выделена, а она является простым числом и меньше тройки. Это меня и смутило. А предложил потому, что за O(~nlogn) работает, я варианта быстрее не знаю.
А, нет, между ними же не может идти простых чисел. Еще одно условие в 40 строку добавить(если число простое, то выходить из цикла)
и алгоритм заработает еще быстрее в лучшем случае.
Yandex
Объявления
15.09.2011, 16:49     Найти самую длинную возрастающую цепочку простых чисел
Ответ Создать тему
Опции темы

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