Najmanjši skupni večkratnik
Sestavi programček, ki sprejme dve celi števili in vrne njun najmanjši
skupni večkratnik. Problem reši z uporabo metod.
Namig
Najmanjši skupni večkratnik se izračuna tako, da pomnožimo vnešeni števili, njun produkt pa delimo z največjim skupnim deliteljem.
Primer za NSD(15, 10) = 5:
15 * 10 / 5 = 30
Napisati je treba metodo NSD, ki izračuna največji skupni delitelj dveh števil. Npr. NSD (15, 10) = 5.
Namig
Največji skupni delitelj lahko izračunamo s pomočjo Evklidovega algoritma. Evklidov algoritem pravi naslednje. Naj bosta $a$ in $b$ celi pozitivni števili. Potem ponavljamo naslednji postopek, dokler je zadnji ostanek $r$ različen od 0.
- Izračunaj ostanek $r$ pri deljenju $a$ z $b$.
- Novi $a$ naj postane $b$.
- Novi $b$ naj postane $r$
- $a = 12$, $b = 33$
- $r = 12$, zato postaneta $a = 33$ in $b = 12$
- $r = 9$, zato postaneta $a = 12$ in $b = 9$
- $r = 3$, zato postaneta $a = 9$ in $b = 3$
- $r = 0$, zato postaneta $a = 3$ in $b = 0$
Rešitev (Java)
import javax.swing.JOptionPane;
public class NajmanjsiSkupniVeckratnik {
public static void main(String[] args) {
// preberemo podatke
String niz1 = JOptionPane.showInputDialog("Vnesi prvo stevilo: ");
String niz2 = JOptionPane.showInputDialog("Vnesi drugo stevilo: ");
int stevilo1 = Integer.parseInt(niz1);
int stevilo2 = Integer.parseInt(niz2);
int odgovor = NSV(stevilo1, stevilo2);
// izpis
JOptionPane.showMessageDialog(null,
"Najmanjsi skupni veckratnik stevil " + stevilo1 + " in "
+ stevilo2 + " je " + odgovor + ".");
}
// metoda vrne največji skupni delitelj števil m in n
public static int NSD(int m, int n) {
int a = m;
int b = n;
while (b > 0) {
int ostanek = a % b;
a = b;
b = ostanek;
}
return a;
}
// najmanjši skupni večkratnik števil m in n izračunamo tako, da zmnožek števil m in n deljivo z njunim največjim skupnim deliteljem
public static int NSV(int m, int n) {
return (m*n)/NSD(m,n);
}
}
Rešitev (C#)
using System;
using System.Collections.Generic;
using System.Text;
namespace NajmanjsiSkupniVeckratnik {
class NajmanjsiSkupniVeckratnik {
static void Main(string[] args) {
// preberemo podatke
Console.Write("Vnesi prvo stevilo: ");
int stevilo1 = Int32.Parse(Console.ReadLine());
Console.Write("Vnesi drugo stevilo: ");
int stevilo2 = Int32.Parse(Console.ReadLine());
int odgovor = NSV(stevilo1, stevilo2);
// izpis
Console.WriteLine("Najmanjsi skupni veckratnik stevil " + stevilo1 + " in "
+ stevilo2 + " je " + odgovor + ".");
Console.ReadKey();
}
// izračunamo največji skupni delitelj
public static int NSD(int m, int n) {
int a = m;
int b = n;
while (b > 0) {
int ostanek = a % b;
a = b;
b = ostanek;
}
return a;
}
// izračunamo najmanjši skupni večkratnik
public static int NSV(int m, int n) {
return (m * n) / NSD(m, n);
}
}
}
Rešitev (Python)
#!/usr/local/bin/python
#-*-encoding: utf-8 -*-
# -*- coding: latin-1 -*-
#najmanjši skupni večkratnik števil m in n izračunamo tako, da zmnožek števil m in n deljivo z njunim največjim skupnim deliteljem
def NSD(m, n):
a = m;
b = n;
while (b > 0):
ostanek = a % b
a = b;
b = ostanek;
return a
def NSV(m, n):
return (m*n)/NSD(m,n)
# metoda vrne največji skupni delitelj števil m in n
# preberemo podatke
m = int(input("Vnesi prvo število: "))
n = int(input("Vnesi drugo število: "))
# izpis
print("Najmanjsi skupni veckratnik stevil",m,"in",n,"je:",NSV(n, m))