Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
49 / 30 / 11
Регистрация: 10.06.2012
Сообщений: 395
1

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

22.07.2015, 17:33. Просмотров 1424. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2015, 17:33
Ответы с готовыми решениями:

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

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

Разложение числа на простые множители
Дано натуральное число n ≥ 2. Составить программу разложения этого числа на простые множители:...

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

10
52 / 52 / 23
Регистрация: 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
2533 / 1193 / 357
Регистрация: 30.11.2013
Сообщений: 3,817
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
49 / 30 / 11
Регистрация: 10.06.2012
Сообщений: 395
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
52 / 52 / 23
Регистрация: 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
49 / 30 / 11
Регистрация: 10.06.2012
Сообщений: 395
23.07.2015, 20:44  [ТС] 6
Krasiosoft, Спасибо большое (конечно лучше бы самому) ,но... Неясен длинный цикл ,пытаюсь разобраться.
0
52 / 52 / 23
Регистрация: 01.06.2015
Сообщений: 189
23.07.2015, 21:01 7
Лучший ответ Сообщение было отмечено sergei60 как решение

Решение

Если вы про:
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
49 / 30 / 11
Регистрация: 10.06.2012
Сообщений: 395
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
52 / 52 / 23
Регистрация: 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
49 / 30 / 11
Регистрация: 10.06.2012
Сообщений: 395
24.07.2015, 19:15  [ТС] 10
Krasiosoft, а можно краткий ход вашей мысли. зачем изменения в цикле ф-ции get_all_divisors ?
0
52 / 52 / 23
Регистрация: 01.06.2015
Сообщений: 189
24.07.2015, 19:24 11
Теперь функция get_lowest_divisor, если не смогла найти делитель, то она просто возвращает число, которое было передано в функцию. Т.е. если делителя нету, то делителем есть само это число.

А цикл в функции get_all_divisors теперь должен выходить по условию, если get_lowest_divisor вернет 1, т.к. единицу дальше некуда уже делить.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.07.2015, 19:24

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

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

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