Найти НОК для всех чисел из файла

270
12 апреля 2018, 13:26

Есть файл, в нём написаны числа. Нужно найти и вывести на экран самое маленькое число, которое делится на все числа из файла, тобишь наименьшее общее кратное. Я написала следующий код:

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
/* Файл: числа. Найти и вывести на экран самое маленькое число, которое делится на все числа из файла */

int main(int argc, char** argv) {
    int num, min=1000000;
    ifstream f("in.txt");
    while(!f.eof()){
        f>>num;
        for (int i=0; i<1000000; i++){
            if (i%num!=0) break;
            else if(i<min){
                min=i;
            }
        }
    }
    cout<<min<<endl;
        return 0;
}

Программа выдаёт 0. Что не так?

Answer 1

Все работает, как написано - на первом же шаге условие if (i%num!=0) не срабатывает, и min обнуляется

Для правильного же нахождения НОК можно задать его tempnok = 1, и далее обычным школьным методом (с использованием НОД) обновлять его на каждом шаге.

для всех чисел из файла:
   tempnok = NOK(tempnok, num)

Edit: Исправление к свежему ответу - достаточно этого:

 while(!f.eof()){
      f >> num;
      tempnok = NOK(tempnok, num);
 { 

Есть и другие варианты - например, разложить все числа на простые множители и использовать произведение максимальных степеней этих множителей (для этого придется еще вести список этих множителей со степенями)

Answer 2

Исправила код, теперь вообще программа виснет...Кажется, я только хуже сделала:(

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
/* Файл: числа. Найти и вывести на экран самое маленькое число, которое делится на все числа из файла */
int NOD (int a, int b)
{
    while (a != b)
    {
        if (a > b)
            a -= b;
        else
            b -= a;
    }
    return a;
}
int NOK (int a, int b)
{
    return a * b / NOD (a, b);
}
int main(int argc, char** argv) {
    int a, count=0, tempnok=1;
    ifstream f("in.txt");
    while(!f.eof()){
        f>>a;
        count++;}
        int num[count];
    for (int i=0; i<count; i++){
        f>>num[i];
            tempnok = NOK(tempnok, num[i]);

    }
    cout<<tempnok<<endl;
        return 0;
}
Answer 3

Никаких проверок на переполнение не производится. Если числа большие, можно использовать библиотеку gmplib (GNU arbitrary precision library). Компилится и собирается как натуральный C, так и как натуральный С++ код.

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
typedef unsigned long long int uint_t;
uint_t gcd(uint_t a, uint_t b);
int main(int argc, char *argv[]) {
    if (argc < 2) {
        printf("usage: prog file\n");
        exit(0);
    }
    FILE *ifs;
    if (NULL == (ifs = fopen(argv[1], "r"))) {
        perror(argv[1]);
        exit(errno);
    }
    uint_t a;
    uint_t b;
    // читаем первое число (не проверяя ни на что)
    fscanf(ifs, "%llu", &a);
    // читаем и обрабатываем остальные числа
    while (1 == fscanf(ifs, "%llu", &b)) {
        a /= gcd(a, b);
        a *= b;
    }
    printf("НОК: %llu\n", a);
    return (0);
}
// Алгоритм Евклида
uint_t gcd(uint_t a, uint_t b) {
    if ((a == 0LLU) || (b == 0LLU)) {
        return 0;
    }
    uint_t c;
    if (a > b) {
        for (;;) {
            c = a % b;
            if (c == 0) {
                return b;
            }
            a = b % c;
            if (a == 0) {
                return c;
            }
            b = c % a;
            if (b == 0) {
                return a;
            }
        }
    } else if (a < b) {
        for (;;) {
            c = b % a;
            if (c == 0) {
                return a;
            }
            b = a % c;
            if (b == 0) {
                return c;
            }
            a = c % b;
            if (a == 0) {
                return b;
            }
        }
    } else {
        return a;
    }
}
READ ALSO
Медленный цикл с векторами в С++

Медленный цикл с векторами в С++

Здравствуйте , есть такой код :

261
Не удаётся открыть источник файла [требует правки]

Не удаётся открыть источник файла [требует правки]

Если открываю готовый проект - не работают стандартные библиотеки

410
Хранение объектов разных типов

Хранение объектов разных типов

Есть абстрактный класс "Organism"Его наследуют 2 классa: "Animals" и "Plants"

244
как можно создавать массив из значения в обьекте

как можно создавать массив из значения в обьекте

как можно получить новый массив состоящий из name например["dima", "Anna", "Denis"], и отдельный массив из lang ["javascript", "php", "html", "css", "python", "ruby"], пробовал через...

196