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

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

Войти
Регистрация
Восстановить пароль
 
sergei60
47 / 28 / 4
Регистрация: 10.06.2012
Сообщений: 374
#1

Разложение на простые множители без рекурсии - C++

22.07.2015, 17:33. Просмотров 727. Ответов 10
Метки нет (Все метки)

Задача такая : Надо написать две функции get_all_divisorts и get_lowest_divisor. Функция main должна вызывать get_all_divisorts , которая в свою очередь имеет цикл :функция get_all_divisorts повторно вызывает get_lowest_divisor , каждый раз заменяя n результатом выражения n / i , где i это найденный делитель. Если возвращается само число n , значит , число простое и цикл должен быть прекращен
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
#include <math.h>
#include <iostream>
using namespace std;
void get_all_divisors(int n);
void get_lowest_divisors(int n);
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
     get_all_divisors(n);
}   
    return 0;
}
void get_lowest_divisor(int n){
    int i;
    if(return (n)){
    cout<<i<<" i простое число";
}
    return 0;
}
    
    void get_all_divisors(int n){//void функция не возвращает зн.
               //но использует инструкцию return для выхода
               //из функции раньше времени.
         int i;
         double sqrt_of_n=sqrt((double)n);
         for( i=2; i<=sqrt_of_n ;i++)
            if(n%i==0){
                cout<<i<<",";
                
                get_lowest_divisor(n);
                             
    
        return ;
    }
        //если делитель не найден,число n -простое
        //напечатать число n и не выполнять дальнейшие вызовы.  
            
cout<<n;
}
Я понимаю,что ошибка где то в функции get_lowest_divisor
C++
1
2
3
4
5
    if(return (n)){
    cout<<i<<" i простое число";
}
    return 0;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2015, 17:33
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Разложение на простые множители без рекурсии (C++):

Разложение на простые множители* - C++
Привет всем, помогите решить, если можно с комментариями что и как, буду очень благодарен, а то у нас курс как-то слишком быстро вперед...

Разложение в простые множители - C++
Дано натуральное число n. Требуется найти его разложение на простые множители. Формат выходных данных Требуется вывести строго...

Разложение натурального числа на простые множители - C++
Выведите разложение натурального числа n &gt; 1 на простые множители. Простые множители должны быть упорядочены по возрастанию и разделены...

Разложение больших целых чисел на простые множители - C++
Нужно написать программу, которая раскладывает числа на простые множители. Я знаю что теоретически надо проверять число на поочередное...

Разложение числа на простые множители (упрощенная). Зацикливание? - C++
Добрый вечер. Написал небольшой код для разложения небольших чисел на простые цифры. По умолчанию число, которое подается на ввод, делится...

Разложение на простые множители заданного натурального числа - C++
Составить программу , печатающую разложение на простые мн0жители заданн0го натУральн0го числа n &gt; 0 (другими словами требуется печатать...

10
Krasiosoft
51 / 51 / 15
Регистрация: 01.06.2015
Сообщений: 189
22.07.2015, 18:13 #2
Функция:
C++
1
void get_lowest_divisor(int n)
Возвращает void, а Вы пытаетесь вернуть число: return 0;

А что означает это:
C++
1
2
if(return (n)){
}
?
0
rikimaru2013
C++ Game Dev
2471 / 1140 / 241
Регистрация: 30.11.2013
Сообщений: 3,709
22.07.2015, 18:25 #3
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
#include <math.h>
#include <iostream>
using namespace std;
void get_all_divisors( int n );
int get_next_divisor( int current_delitel, int number );
 
int main( )
{
    int n = 0;  // возьмите за правило инициализировать значение локальных переменных (далее полей) значениями по умолчанию - для int это 0 
    while(n == 0)
    {
        cout << endl;
        cout << "введем число(кроме 0) ";
        cin >> n;       
        if(n!=0)
            get_all_divisors( n );
    }
    return 0;
}
int get_next_divisor( int current_delitel,  int number ) 
// если метод должен вызываться несколько раз и возвращать верное значение, то ему должно приходить разные значения
// если метод возвращает значения у него тип возвращаемого значения не может быть void
 
{
    // алгоритм поиска следующего делителя
    // приходит нам предыдущий делитель, а мы ищем следующий или вовзращаем i == number, что кстате является его делителем)
    int i = current_delitel;    
    while(i < number)
    {
        if(number % i != 0)
            i++;        
        else
            break;      
    }
    return i;
}
 
void get_all_divisors( int n )
{
    int* arr = new int[188];
    int index = 0;
    int seach = 1;
    while(seach < n)
    {
        seach = get_next_divisor( seach, n );
        arr[index] = seach;
 
        index++;
        seach++;        
    }
 
 
    for(int i = 0; i < index; ++i)
    {
        cout << arr[i] << endl;
    }
 
}
1
sergei60
47 / 28 / 4
Регистрация: 10.06.2012
Сообщений: 374
23.07.2015, 07:51  [ТС] #4
rikimaru2013, Первоначальный код был таким .и надо его переделать в задании. Спасибо конечно за ответ ,но до arr я еще не дошел в книге .
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
#include <math.h>
#include <iostream>
using namespace std;
void get_divisors(int n);
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
    get_divisors(n);
}   
    return 0;
}
    void get_divisors(int n){//void функция не возвращает зн.
               //но использует инструкцию return для выхода
               //из функции раньше времени.
         int i;
         double sqrt_of_n=sqrt((double)n);
         for( i=2; i<=sqrt_of_n ;i++)
            if(n%i==0){
                cout<<i<<",";
                
                get_divisors( n/i);//возвращает и печатает i 
                             
    
        return ;
    }
        //если делитель не найден,число n -простое
        //напечатать число n и не выполнять дальнейшие вызовы.  
            
cout<<n;
}
Добавлено через 11 часов 26 минут
Задача такая : Надо написать две функции get_all_divisorts и get_lowest_divisor. Функция main должна вызывать get_all_divisorts , которая в свою очередь имеет цикл :функция get_all_divisorts повторно вызывает get_lowest_divisor , каждый раз заменяя n результатом выражения n / i , где i это найденный делитель. Если возвращается само число n , значит , число простое и цикл должен быть прекращен

Добавлено через 1 час 8 минут
Смотрю на начальный код с рекурсией , где все делается в функции void get_divisors(int n). Ход мысли таков . Вместо рекурсии я должен вызвать новую функцию и передать ей полученную в цикле i. В этой новой функции , которую назвали get_lowest_divisor , я должен сделать действие n / i и if( n/i==0 ) , то вернуть назад это новое значение в функцию
void get_divisors(int n) , там оно добавится в список для выведения и все продолжится как в первом коде . Где ошибка в моих рассуждениях , если ошибки нет , то как реализовать это ?

Добавлено через 35 минут
Просьба спецов проверить ,правильное ли решение ?
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
#include <math.h>
#include <iostream>
using namespace std;
int get_lowest_divisor(int );
void get_divisors(int n);
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
    get_divisors(n);
}   
    return 0;
}
    void get_divisors(int n){//void функция не возвращает зн.
               //но использует инструкцию return для выхода
               //из функции раньше времени.
         int i;
         double sqrt_of_n=sqrt((double)n);
         for( i=2; i<=sqrt_of_n ;i++)
            if(n%i==0){
            cout<<i<<",";
                get_lowest_divisor(n/i);
    return ;
    }
    cout<<n;
    }
int get_lowest_divisor(int n){
    int i;
    if(n/i==0)
    get_divisors(n);
    
}
0
Krasiosoft
51 / 51 / 15
Регистрация: 01.06.2015
Сообщений: 189
23.07.2015, 19:26 #5
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
#include <iostream>
 
using namespace std;
 
int get_lowest_divisor(int number){
    for(int i=2;i<=number;i++){
        if( number%i == 0) return i;
    }
    return 0;
}
 
void get_all_divisors(int number){
    for(int divisor=get_lowest_divisor( number );divisor;divisor=get_lowest_divisor( number/=divisor ) ){
        cout << divisor << " ";
    }
}
 
int main(){
 
    int n;
    do{
        cout << "Input number: ";
        cin >> n;
    }while(n == 0);
 
    get_all_divisors(n);
 
    return 0;
}
Что-то вроде этого нужно?
1
sergei60
47 / 28 / 4
Регистрация: 10.06.2012
Сообщений: 374
23.07.2015, 20:44  [ТС] #6
Krasiosoft, Спасибо большое (конечно лучше бы самому) ,но... Неясен длинный цикл ,пытаюсь разобраться.
0
Krasiosoft
51 / 51 / 15
Регистрация: 01.06.2015
Сообщений: 189
23.07.2015, 21:01 #7
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если вы про:
C++ (Qt)
1
for(int divisor=get_lowest_divisor( number );divisor;divisor=get_lowest_divisor( number/=divisor ) )
То тут:

Инициализация: int divisor=get_lowest_divisor( number ), т.е. берем первый делитель от оригинального числа
Условие: divisor, т.е. пока divisor не равен 0
Изменения значений на следующем шаге: divisor=get_lowest_divisor( number/=divisor ), т.е. делим число на делитель и передаем результат этого в get_lowest_divisor
1
sergei60
47 / 28 / 4
Регистрация: 10.06.2012
Сообщений: 374
24.07.2015, 17:30  [ТС] #8
Krasiosoft, Впервоначальном коде у меня есть строчка double sqrt_of_n=sqrt((double)n); то есть в цикле я нахожу простое число из корня ,для этого используется математическая функция sqrt и в цикле for( i=2; i<=sqrt_of_n ;i++). Пытаясь подставить корень в окончательный код ,программа перестает правильно работать . Она обрабатывает не все значения. Что я делаю не так ? Вот причесанный окончательный код.
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
#include <iostream>
 #include <cmath>
using namespace std;
 
int get_lowest_divisor(int n){
   double sqrt_of_n=sqrt((double)n);
         for( int i=2; i<=sqrt_of_n ;i++){
        if( n%i == 0) return i;
    }
    return 0;
}
 
void get_all_divisors(int n){
    for(int i=get_lowest_divisor(n);i;i=get_lowest_divisor(n=n/i)){
        cout << i << " ";
    }
}
 //инициализация: int i=get_lowest_divisor( n );
 //берем первый делитель от оригинального числа
 //Условие: i, т.е.пока i не равно 0
 //изменение значения на след. шаге  i=get_lowest_divisor( n/=i )
 //т.е. делим число на делитель и передаем результат этого
 //  в функцию get_lowest_divisor
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
    get_all_divisors(n);
}
    return 0;
}
0
Krasiosoft
51 / 51 / 15
Регистрация: 01.06.2015
Сообщений: 189
24.07.2015, 18:26 #9
Тогда будет так:

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
#include <iostream>
#include <cmath>
 
using namespace std;
 
int get_lowest_divisor(int n){
    double sqrt_of_n = sqrt((double)n);
    for(int i=2; i<=sqrt_of_n ;i++){
        if( n%i == 0) return i;
    }
    return n;
}
 
void get_all_divisors(int n){
    if(n!=1){
        for(int i=get_lowest_divisor(n);i!=1;i=get_lowest_divisor(n=n/i)){
            cout << i << " ";
        }
    }else{
        cout << "1";
    }
}
 
int main () {
    int n;
    while (1){
        cout<<endl;
        cout<<"введем число(кроме 0) ";
        cin>>n;
        if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
            break;
        get_all_divisors(n);
    }
    return 0;
}
1
sergei60
47 / 28 / 4
Регистрация: 10.06.2012
Сообщений: 374
24.07.2015, 19:15  [ТС] #10
Krasiosoft, а можно краткий ход вашей мысли. зачем изменения в цикле ф-ции get_all_divisors ?
0
Krasiosoft
51 / 51 / 15
Регистрация: 01.06.2015
Сообщений: 189
24.07.2015, 19:24 #11
Теперь функция get_lowest_divisor, если не смогла найти делитель, то она просто возвращает число, которое было передано в функцию. Т.е. если делителя нету, то делителем есть само это число.

А цикл в функции get_all_divisors теперь должен выходить по условию, если get_lowest_divisor вернет 1, т.к. единицу дальше некуда уже делить.
1
24.07.2015, 19:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2015, 19:24
Привет! Вот еще темы с ответами:

Описать функцию, находящую разложение заданного натурального числа на простые множители - C++
Помогите написать программу, пожалуйста Описать функцию factors(a, n, F), находящую разложение натурального числа a на простые множители....

Разложение числа на множители - C++
var s1,s2,n: longint; f: integer; begin write('vvedite natural chislo '); readln(n); f:=0; s1:=1; ...

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

Определить простые множители - C++
Задание: Составить программу определения, является ли данное число простым. Если число не является простым, то определить все его простые...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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