Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
#1

Найти наименьшее общее кратное (НОК) n натуральных чисел - C++

15.12.2011, 23:33. Просмотров 2289. Ответов 3
Метки нет (Все метки)

Есть задача:
условие
НОК

Найти наименьшее общее кратное (НОК) n натуральных чисел.

Технические условия

Вход

В первой строке задано количество чисел n (1 < n < 21). Во второй строке находится n натуральных чисел, не превышающих 100 и разделенных пробелом.

Выход

НОК заданных чисел.


Тут нормальное условие
Написал обычный алгоритм типа НОК = (a*b)/Nod(a,b); Но получается превышение лимита времени на последнем тесте. Как с этим бороться?
http://www.cyberforum.ru/cpp-beginners/thread281239.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2011, 23:33
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти наименьшее общее кратное (НОК) n натуральных чисел (C++):

Найти НОК (наименьшее общее кратное) массива натуральных чисел
Найти НОК (наименьшее общее кратное) массива натуральных чисел. Спасибо за...

Найти наименьшее общее кратное (НОК) n натуральных чисел (оптимизировать код)
Здравствуйте! Вот еще одна несложная задачка, однако 10/11 (последний тест не...

Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B
Задача 7. Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и...

Найти НОК (наименьшее общее кратное) двух введённых чисел
Найти НОК (наименьшее общее кратное) двух введённых чисел. Спасибо за помощь

Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел.
Найти наибольший общий делитель и наименьшее общее кратное двух введенных...

3
VaniaKosmos
0 / 0 / 0
Регистрация: 07.03.2014
Сообщений: 3
07.03.2014, 16:24 #2
Предельно простая задача даже для начинающего как я. Нужно лишь чуток подумать)
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
int nsd (int a, int b){ //НОД
    
    if (b == 0) {
        return a;
    }
    
    return nsd(b, a%b);
}
 
int main(){
 
    int n, b, c = 1;
    
    cin >> n; //водим количество наших чисел
    
    for(int i = 0; i < n; i++){
        
        cin >> b; //вводим каждое число отдельно
        
        c = c*b / nsd(c, b); //класическое нахождее НОД от двух переменных
    }
    cout << c << endl;  //вот и результат
    return 0;
}
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.03.2014, 00:16  [ТС] #3
VaniaKosmos, а ты сдать ее попробуй туда. Я подумал - тут длинка нужна и всё.
0
VaniaKosmos
0 / 0 / 0
Регистрация: 07.03.2014
Сообщений: 3
12.03.2014, 10:09 #4
Странно. В подобной задаче с таким использованием НОК все прошло. Даже с лонг лонгом 1 тест не проходит. Буть может тут специфический случай. Потому что явную ошибку я не вижу(
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
#include "stdio.h"
#include "math.h"
#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
LL nsd (LL a, LL b) {
    if (b == 0)
        return a;
    return nsd(b, a%b);
}
 
int main(){
    
    int n, b;
    LL c = 1;
    
    cin >> n; //водим количество наших чисел
    
    for(int i = 0; i < n; i++){
        
        cin >> b; //вводим каждое число отдельно
        
        c = c*b / nsd(c, b); //класическое нахождее НОД от двух переменных
    }
    cout << c << endl;  //вот и результат
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2014, 10:09
Привет! Вот еще темы с решениями:

Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел
Напишите пожалуйста код =)

Написать программу, вычисляющую НОК (наименьшее общее кратное) двух целых чисел
2. Написать программу, вычисляющую НОК (наименьшее общее кратное) двух целых...

Вычислить наименьшее общее кратное двух натуральных чисел
Написать программу, вычисляющую наименьшее общее кратное двух натуральных чисел...

Определить наименьшее общее кратное двух натуральных чисел
вот мой код. выдаёт одну ошибку. помогите пожалуйста найти. ...


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

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

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