Algoritmus pro počítání – Java – Fórum – Programujte.com

Potřeboval bych poradit s tímto:

mám vytvořit program, který z obdélníkových karet o zadaných rozměrech a [mm] a b [mm] spočte a vypíše velikost strany nejmenšího čtverce, který je možno z karet vytvořit a dále určí a vypíše, kolik karet bude zapotřebí. Hodnoty a a b jsou celá čísla, která jsou zadána na jednom řádku a navzájem oddělena mezerou.

#1 K4BlOs
Na jaké jsi škole, že tam umí vymýšlet tak hezká zadání?

U nás by zřejmě narazili na matematické nedostatky žáků.

Každopádně k algoritmu - podle mně jde o to najít největšího společného dělitele, tím podělit strany a vyjde ti počet karet v opačném směru.

Příklady:

kartax kartay nsd početx počety

3          3         3        1          1

3           4        1        4         3

3           6        3        2          1

6         15        3        5          2

12        32       4        8          3

#2 JoDiK
Ano toto mě tyky napadlo jenže horší je to se zapsáním do Javy. Zkoušel jsem to přes cykly for a while jenže mi to pořád neběhá jak má. Nevíš jak na to?

#3 K4BlOs
Jak na co?

Jako jak najít největšího společného dělitele?

Není tento algoritmus popsán na internetu?

To ostatní už je matematika základní školy, žádné cykly...

#4 JoDiK

...v tomhle případě to má být nejmenší společný násobek ne?

#5 reciproke
Aha, asi jsem se špatně vyjádřil, jde o největšího společného dělitele, jestli je to totéž co nejmenší společný násobek tak to je ono.

co? no to není ani omylem.

 To já se možná špatně vyjádřil.... má skládat obdélníkové karty do nejmenšího čtverce, takže potřebuje určit jeho stranu. A tu snad určí jako nejmenší společný násobek stran obdélníka.
 

a na to kdyz by chtel brutal force metodu tak jen cyklus od  "a" do a*b s krokem "a"  a skoncit jakmile je  aktualni hodnota bezezbytku delitelna b :)  (a bude to i rychlejsi nez delat rozklad na prvocisla)

jenže o takové cykly jsem se pokoušel, ale nevim jak je přesně napsat :(

tak dej sem ukazku co si vyrobil, pak se s tim da pokracovat dal

teď jsem v práci až budu doma tak sem něco hodím

#7 reciproke
Já jsem teď trochu mimo, jaký je teda například nejmenší společný násobek hodnot 12 a 32???

tak vemem to algoritmicky se zbytkem po deleni (mozna by bylo lepsi prohodit aby se krokovalo vetsi hodnotou):

32 % 12  = 8

64 % 12  = 4

96 % 12 =  0  ->  nejmensi spolecny nasobek je 96

(mimochodem: "Největší společný dělitel dvou čísel je číslo takové, které je obě vydělí beze zbytku"  http://maths.cz/clanky/nejvetsi-spolecny-delitel.html tj. neni to to co potrebujeme...)

#13 KIIV
Aha, takže vlastně dojdeme ke stejnému výsledku jako já přes toho největšího společného dělitele - což je 3 takže mi vyjde 8 karet na šířku neboli 8x12=96

Teď je otázka co je jednodušší - hledat NSD nebo NSN?

#14 JoDiK
Oprava, samozřejmě 4!!

Přehlídl jsem se, 3 je počet karet!

Výpočet je správně...

#15 JoDiK
No a Eukleidův algoritmus je přece docela rychlý a jednoduchý...

#15 JoDiK
Ok, ale pro mě a většinu, kdo neví hned jak na to bude na první pohled zřejmější ten násobek. 

#17 reciproke
No a to je přece ta krása programování, že tě pokaždé někdo překvapí jiným a někdy i jednodušším řešením...

Já jsem prostě nešel přes ten čtverec, ale přes ty karty...

Aplikoval jsem metodu pokus/omyl a na to metodu postupného zobecňování a došel k tomuto výsledku...

tak zde je muj kod:

import java.util.*;

public class XXX {
private static Scanner sc;

public static int gcd(int a, int b) {
  if (a < 1 || b < 1) throw new IllegalArgumentException();
  while (b != 0) {
  int tmp = a;
  a = b;
  b = tmp % b;
  }
  return a;
  }

public static void main(String[] args) {
  sc = new Scanner(System.in);
     System.out.println("Zadej rozmery karty");
     String s = sc.nextLine();
     String[] st = s.split(" ");
     int a = Integer.parseInt(st[0]);
     int b = Integer.parseInt(st[1]);
  System.out.println("---Vysledky---");
  int vysledek = gcd(a, b);
  System.out.println(+vysledek);
}
}

tu metodu gcd jsem nasel na netu, ale nejak mi to zrejme nedela to co ma

Tak jsem to nakonec upravil jinak a už mi to běhá jak má díky všem

#20 K4BlOs
Tak se pochlub, jak jsi to upravil...

Tak zde je muj kod:

import java.util.*;

public class XXX {
private static Scanner sc;

public static void main(String[] args) {
  sc = new Scanner(System.in);
     System.out.println("Zadej rozmer karty");
     String s = sc.nextLine();
     String[] st = s.split(" ");
     int a = Integer.parseInt(st[0]);
     int b = Integer.parseInt(st[1]);
    
     int NSN;
     boolean delitelne;
     if (a>b) NSN=a-1; else NSN=b-1;
     do{
       NSN++;
       delitelne=true;
       if((NSN%a==0)&(NSN%b==0))                                   
                       delitelne=false;
      }while(delitelne);
    
     int pocetKaret = ((NSN/a)*(NSN/b));
    
  System.out.println("---Vysledky---");
  System.out.println("Strana nejmensiho ctverce = " + NSN );
  System.out.println("Pocet karet = " + pocetKaret );
}
}

Jenze ted tu mam dalsi program a zase si nevim rady. 

Přečtěte z klávesnice přirozené číslo, které bude udávat počet členů Fibonacciho posloupnosti (0, 1, 1, 2, 3, 5, ...), kde nultý člen posloupnosti je 0, první člen je 1, druhý člen je 1, atd. Vytvořte pole, do kterého vypočtete požadovaný počet členů této posloupnosti. Pro výpočet členů použijte metodu int[] dalsiClen(int[] pole), kde pole je momentálně platné, zcela zaplněné pole a metoda nejprve vytvoří pole o jeden prvek větší a pak součtem dvou posledních členů původního pole zjistí hodnotu dalšího členu. Předchozí členy posloupnosti překopíruje z původního pole. Nově vytvořené pole je metodou vráceno. Metoda bude kromě výpočtu a uložení nového členu vždy kontrolně tisknout i celé nové pole. Pozn: tento algoritmus je neefektivní, ale to není zatím náš problém.

Vstup: počet členů Fib. posloupnosti

Vystup: 

Zadej pocet clenu posloupnosti: 0
---Vysledky---
[0]

Zadej pocet clenu posloupnosti: 1
---Vysledky---
[0]
[0, 1]

Zadej pocet clenu posloupnosti: 2
---Vysledky---
[0]
[0, 1]
[0, 1, 1]

Zadej pocet clenu posloupnosti: 3
---Vysledky---
[0]
[0, 1]
[0, 1, 1]
[0, 1, 1, 2]

Zadej pocet clenu posloupnosti: 5
---Vysledky---
[0]
[0, 1]
[0, 1, 1]
[0, 1, 1, 2]
[0, 1, 1, 2, 3]
[0, 1, 1, 2, 3, 5]

#23 K4BlOs
Máš už něco, nebo s čím konrétně si nevíš rady.?

Jinak ještě k předchozímu gcd se chovalo korektně. A tvé konečné řešení není zrovna efektivní s krokem po 1, rychlejší řešení máš dle #8, ale když se spokojíš s fukčností....

no já zatim vubec nevim kde zacit.pokusil jsem se o vytvoreni metody pro vypocet n-teho clenu ktery zadam z klavesnice ale myslim si ze to mam uplne spatne :D

import java.util.*;

public class XXX {
public static Scanner sc = new Scanner(System.in);

static int[] dalsiClen(int[] poole) {
  int n = sc.nextInt();
     int[] pole = new int[n];
     for (int i = 0;  i < pole.length;  i++) {
      pole[i] = ((n-1)+(n-2));
     }
  return pole;
    }

public static void main(String[] args) {
  System.out.println("Zadej pocet clenu posloupnosti: ");
 
  System.out.println("---Vysledky---");
}
}

#25 K4BlOs

Každopádně první 3 hodnoty 0, 1, 1 musíš zadat do pole v programu. A pak příslušně voláš metodu pro výpočet dalšího, ve které žádné "n" nenačítáš, vytvoříš nové o 1 delší než stávající předané metodě

int[] nove = new int[pole.length+1];

následně ve foru nebo pomocí System.arraycopy() překopíruješ stávající hodnoty. Nakonec spočteš poslední hodnotu, to je jen hra s indexy a vrátíš to nové.

nějak takto?

static int[] dalsiClen(int[] pole) {
  int[] nove = new int[pole.length+1];
  nove[0] = 0;
  nove[1] = 1;
  nove[2] = 1;
  for (int i = 2; i < nove.length; i++) {
   nove[i] = nove[i - 1] + nove[i - 2];
  }
  return nove;
    }

#27 K4BlOs
no já jsem to  trošku zamotal do sebe... dalsiClen bude vypadat následovně  

static int[] dalsiClen(int[] pole){
        
        // délka původního
        int length = pole.length;   
        // vytvoří nové        
        int[] nove = new int[length+1];
        //překopíruje stávající prvky
        for (int i = 0; i < pole.length; i++) {
            nove[i] = pole[i];
        } 
        // nebo tak
        //System.arraycopy(pole, 0, nove, 0, pole.length);
        
        // vypočítá poslední člen, !!! length je délka původního !!!
        nove[length] = nove[length-1]+nove[length-2];
        // vrátí nové
        return nove;        
    }

V mainu budeš mít vytvořené to pole o 3 prvních, které budeš předávat dané metodě. 

 int pole[] = {0,1,1};

Ale další členy potřebuješ vypočítat pro n > 3, takže pro první 3 to volání dalsiClen přeskočíš a jen vypíšeš to co máš...

#28 reciproke
nějak nechápu to, že budu předávat int pole[] = {0,1,1} dané metodě.Já myslel že té metodě mám předat číslo do kterého mi má spočítat tu posloupnost?

#29 K4BlOs
...jo no předávat tohle pole, moje nepřesnost. Tohle pole té metodě předáš jen jednou pro výpočet třetího členu a pak vždy to rozšířené o další prvek. Jinak proč se předává pole a né jinak? ...protože to máš v zadání.

 Zadej pocet clenu posloupnosti: 0
---Vysledky---
[0]

Zadej pocet clenu posloupnosti: 1
---Vysledky---
[0]
[0, 1]

Jinak ještě trošku nesrovnalost, příklad požaduje zadat počet členů, ale vypysuje po N-tý člen.
 

#30 reciproke
ja sem z toho jelen.Vubec se v tech polich nevyznam. Kdyz dam vypsat 4 clen tak mi to hodi nejake nesmysly "[I@b42cbf" asi se zase vratim k nějakému vysvětlení o polích abych vůbec věděl co to je :)

#32 K4BlOs
tohle snad pomůže

ehm, omlouvám se na Fibonacciho posloupnost samozřejmě stačí první 2 členy a ne 3  

tak a ted po vsech tech mouder jsem z toho jeste vic zmatenej nez sem byl. Mohl bys mi prosim te napsat podrobnejsi navod? ja sem fakt zacatecnik a metodou pokus omyl to budu delat 100 let :D

#35 K4BlOs
však o to jde, naučit se to ne? V jakém stavu tedy jsi, že jsi skončil na polích?

no ja sem si to zkusil zatim udelat bez te pocitaci metody ciste jenom na tu posloupnost a to myslim ze mi funguje, ale nevim jak mam ytvořit pole, do kterého vypíšu těch "n" členů tý posloupnosti

#37 K4BlOs
jo a tady je kod:

public static void main(String[] args) {
  System.out.println("Zadej pocet clenu posloupnosti: ");
  int n = sc.nextInt();
  int[] posloupnost = new int[n];
  posloupnost[0] = 0;
  posloupnost[1] = 1;
  for (int i = 2; i < posloupnost.length; i++) {
   posloupnost[i] = posloupnost[i - 1] + posloupnost[i - 2];
  }
  System.out.println(posloupnost[posloupnost.length - 1]);
}

#38 K4BlOs
Tak jednotlivým prvkům se dostaneš stejným způsobem jako do nich zapisuješ. Tahle třeba vypíšeš celou posloupnost.

for (int i = 0; i < posloupnost.length; i++) {
	System.out.println(posloupnost[i]);
}

Jinak koukam že ta metoda nemá být jen počítací, takže to trochu mění věc.

PS používej na kod příslušné prostředky ikona "<?"

super tak ted uz alespon vydim vsechny v rade. Co presne znamena  

 int[] dalsiClen(int[] pole)

tim vytvorim pole dalsiClen ktere bude mit podpole pole?

#40 K4BlOs
to by jsi snad už mohl vědět ne?

Je to metoda která přijímá pole a vrací také celočíselné pole.

#40 K4BlOs
Hlavní je pořádně si přečíst zadání a pochopit ho, trošku mou myšlenku zkazila ta metoda, která má i vypisovat posloupnost. Vyjasni si tu nesrovnalost co se má zadávat a co vypisovat. Tady to máš na N prvků z posloupnosti, jen si doformátuj ten výstup.

import java.util.*;

public class XXX {
    
    public static Scanner sc = new Scanner(System.in);

    static int[] dalsiClen(int[] pole){
        
        int[] nove;
          
        // vytvoří nové        
        if(pole == null){
            // pole je null -> nové s jedním prvkem {0}
            nove = new int[1];
            nove[0] = 0;
        } else if (pole.length == 1) {
            // pole mělo jeden prvek -> další bude mít 2 {0,1}
            nove = new int[2];
            nove[0] = 0;
            nove[1] = 1;
        } else {
            // pole mělo x, další bude x+1 prvků
            nove = new int[pole.length+1];
            //překopíruje stávající členy
            for (int i = 0; i < pole.length; i++) {
                nove[i] = pole[i];
            } 
            // nebo tak
            //System.arraycopy(pole, 0, nove, 0, pole.length);
            
            // vypočítá poslední člen
            nove[pole.length] = nove[pole.length-1]+nove[pole.length-2];
        }
        
            // vypíše aktuálně známý počet členů
            for (int j = 0; j < nove.length; j++) {
                System.out.print(nove[j] + " ");                
            }
            System.out.println();        
        
        // vrátí pole doplněné o další člen
        return nove;        
    }
    
    public static void main(String[] args) {
        
        int pole[] = null;
        System.out.print("Zadejte pocet clenu: ");
        int clen = sc.nextInt();        
        System.out.println("---Vysledky---");
        
        // spočítá N členů
        for (int i = 0; i < clen; i++) {
            // 1 volání -> 1 další člen + výpis
            pole = dalsiClen(pole);                    
        }        
    }
}

   díky moc a já se tady trápil celej den s ani né třetinou tohoto.no jo kdo umí, umí    

#43 K4BlOs
ale tohle jsou základy algoritmizace... nebýt mé nepozornosti tak ti to tak lehce nedam. A teď co z toho máš???

tak tu mam k tomu jeste jeden dotaz.
vystup by mel vypadat takto:

Zadej pocet clenu posloupnosti: 3
---Vysledky---
[0]
[0, 1]
[0, 1, 1]
[0, 1, 1, 2]

ale muj vystup vypada takhle

Zadejte pocet clenu posloupnosti: 3
---Vysledky---
[0]
[0, 1][0, 1]
[0, 1, 1][0, 1, 1][0, 1, 1]

nevim proc, ale at sem zkousel cokoli tak se mi porad ty radky opakuji a navic mi tam chybi jeste jeden radek kterej by mel mit na konci cislo 2.

zde je muj program:

import java.util.*;

public class XXX {
    
    public static Scanner sc = new Scanner(System.in);

    static int[] dalsiClen(int[] pole){
        
        int[] nove;     
        if(pole == null) {
            nove = new int[1];
            nove[0] = 0;
        } else if (pole.length == 1) {
            nove = new int[2];
            nove[0] = 0;
            nove[1] = 1;
        } else {
            nove = new int[pole.length+1];
            //for (int i = 0; i < pole.length; i++) {
            //    nove[i] = pole[i];
            //} 
            System.arraycopy(pole, 0, nove, 0, pole.length);
            nove[pole.length] = nove[pole.length-1]+nove[pole.length-2];
        }
            for (int j = 0; j < nove.length; j++) {
            	//System.out.print(nove[j] + " ");
            	//System.out.format( "[" + "%3d, ", nove[j] + "]");
            	System.out.print(Arrays.toString(nove));
            }
            System.out.println();
        return nove;        
    }
    
    public static void main(String[] args) {
        
        int pole[] = null;
        System.out.print("Zadejte pocet clenu posloupnosti: ");
        int clen = sc.nextInt();        
        System.out.println("---Vysledky---");
        if (clen == 0) {
        	System.out.println("[0]");
        }
        for (int i = 0; i < clen; i++) {
            pole = dalsiClen(pole);                    
        }        
    }
}

#45 K4BlOs
predpokladejme ze chyba vznika nekde kolem vypisu (doslova)

jenže já sem zkoušel různé varianty a už mě nenapadá jak jinak to vypsat :(

#47 K4BlOs
že ti to vypisuje o člen méně, po třetí opakuji v příkladu je nekonzistence. Program se ptá na počet členů a při tom vypisuje po N-tý člen. Pokud se chceš příkladu držet, snad není tak těžké v daném cyklu ještě jednou zalovat výpočet pro další člen.

Ohledně výpisu se na nějké tvé všechny varianty vykašli a začni už také trochu přemýšlet... Když už můžeš použít "Arrays.toString()" tak přemýšlet potřebuješ už jen minimálně. Když nevidíš jak se to chová, tak si zkus ručně nadefinovat pole a v zápětí vypsat.

Jinak jsem rád že umíš umazávat komentáře, s tím se dostaneš daleko