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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Чем отличается С++ от Visual С++? http://www.cyberforum.ru/cpp-beginners/thread350822.html
Здравствуете товарищи программисты! Только начал изучать язык программирования С++ и возникло пару вопросов. Чем отличается С++ от Visual С++? И еще посаветуйте какую-нибудь литературу на русском языке, для понятия основ языка.(В Универе дают только на английском) В поисковике искать не хотел, т.к. у бывалых программистов спросить лучше.Спасибо.
C++ как кодить на с в Microsoft visual studio 2010 первый раз встречаюсь с вижлой.как кодить на с в Microsoft visual studio 2010?обьясните поподробнее как что где создавать и как компилировать http://www.cyberforum.ru/cpp-beginners/thread350801.html
Solutions manual по книге c++ how to programm C++
Апну темку и заодно мб, кто-нибудь имеет еще 1 книжку. Нужен solutions manual по книге c++ how to programm (5 издания). Заранее спс.
Описать класс, реализующий бинарное дерево C++
Здравствуйте! Возникли проблемы с реализацией одной программы ....Описать класс, реализующий бинарное дерево, обладающее возможностью добавления новых элементов, удаления существующих, поиска элемента по ключу, а также последовательного доступа ко всем элементам. Написать программу, использующую этот класс для представления англо-русского словаря. Программа должна содержать меню, позволяющее...
C++ Не получаеться решить http://www.cyberforum.ru/cpp-beginners/thread350749.html
Дана функция y(x)=Ax2+Bx+C, где A – количество букв в фамилии студента, B количество букв в имени студента, C количество букв в отчестве студента. Для функции y(x) составить программу построения таблицы значений функции при изменении аргумента от L до R с шагом T. В каждой строке выводить значения аргумента и соответствующее ему значение функции. Кроме того, в конце таблицы напечатать...
C++ Как удалить все элементы из очереди (queue) Есть очередь queue и в ней элементы, как удалить их все чтобы очередь осталась пустой? подробнее

Показать сообщение отдельно
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
15.09.2011, 14:20     Найти самую длинную возрастающую цепочку простых чисел
Ниже: трэд, нить, поток - синонимы, мэйн-трэд - основной поток процесса.
Касательно собственно вычислений. Старался комментировать подробно. Общий принцип: считать последовательность в массив, выделить простые. После этого можно выделять возрастающие подпоследовательности и искать наидлиннейшую или еще каким либо образом с ними работать. Заголовочник 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
 
Текущее время: 05:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru