Sázení česneku – Java – Fórum – Programujte.com

Dobrý den, dostal jsem úkol a potřebuji nějak pomoci, nějak nerozumím, jak by měl algoritmus tohoto programu vypadat..

Zatím jsem vytvořil jednorozměrné pole a do celého pole jsem dal samé cibule, nevím si rady, jak dál

Děkuji za každou radu

Zadání:

Cibule a česnek

? Jste zahradníci a chcete sázet jeden dlouhý
řádek cibule a česneku
? Nechcete sázet dva česneky těsně vedle sebe,
vždy mezi ně zasadíte minimálně jednu cibuli
? Protože se česnek sám se sebou nesnáší
? Kolika různými způsoby můžete řádek osázet?
? Vypište všechny možnosti a spočtěte jejich počet
? Řádek bude vždy obsahovat N sazeniček
? N načtěte ze vstupu od uživatele

Celý řádek cibule ... a hned máš jednu možnost. Doporučuji vzít si čtverečkovaný papír a například pro N=10 si vypsat všechny možnosti, které tě napadnou. Třeba z toho vzejde nejenom cibule a česnek, ale i ten algoritmus :).

#2 liborb
napadlo mě, vypisovat to jako binární soustavu..

0001

0010

0011 - nelze

0100

Jedničky reprezentují česneky. A když budou dvě 1 vedle sebe, tak to nevypisovat.

Jenom vůbec nevim jak to napsat, mohl byste mi někdo alespoň trošku nastínit, jak postupně vypsat ten binární kód?

Asi bys měl ohlídat počet česneku a cibule........takže když česneku bude N, tak cibule musí být minimálně N-1. 

Není mi jasný tvoje zadání......uživatel zadá počet sazeniček.......skvělý a jako to jsou cibule a česnek dohromady?? Nechápu.

#3 Lojza
To tě napadlo správně. A jak to udělat?

Představ si, že uživatel zadá nějaké N. Ty vytvoříš pole o délce N + 1. Nejprve to pole celé vynuluješ - zasázíš cibuli (jen tak mimochodem je to první varianta).

Vstoupíš do cyklu - pro tento případ by se pěkně hodil s podmínkou na konci (do-while). V těle tohoto cyklu nejprve zkontroluješ, jestli je aktuální varianta platná, tj. opět cyklem (index I) projdeš pole od 0 do N - 1 a budeš koukat, jestli hodnota na I a I + 1 v poli je 1, a pokud ano, tak máš 2 česneky vedle sebe, a to "nelze". Po kontrole varianty si připravíš další.

Zjednodušeně řečeno - cibule je 0 a česnek je 1 - vezmeš číslo na indexu 0 a zvedneš ho o 1. Pokud bude rovno 1, tak máš další variantu, jinak (byla by tam dvojka) ji změníš na 0 a zvedneš hodnotu na indexu 1. Pokud je tam 1, tak máš další variantu, Pokud je tam 2, tak opět nuluješ (index 1) a jdeš na index 2. A takto až do indexu N + 1.

Celé se to dá realizovat jedním cyklem s daným počtem opakování, ve kterém bude nejprve inkrement na daném indexu, následně podmínka s případným break nebo v opačném případě vynulování hodnoty v poli na aktuálním indexu.

A proč mít pole o délce N + 1? No protože hlavní cyklus (do-while) pojede dokud je hodnota v poli na tomto posledním přidaném indexu 0. Ve chvíli, kdy se tam objeví 1, tak si prošel všechny varianty a program může skončit.

Hezká úloha, taky se ten algoritmus dá zapsat přímo ze zadání s použitím rekurze a následně zoptimalizovat, sloučit některé podmínky případně odstranit rekurzi bude-li třeba, Javu neumím je to v Cčku, ale s tím už si pohraješ (ve výpisu 'C' je cibule a '*' je česnek :-)

#include <stdio.h>

int vysazej_radek(char* array, int pos, int N)
{
  if (pos == N) { // Kdyz jsem vysazel vsechno vypsat radek
    for (int i = 0; i < N; i++) {
      printf("%c", array[i]);
    }
    printf("\n");
    return 1;
  }

  int pocet = 0;
  
  if (pos == 0) { // Kdyz jsem na zacatku radku muzu zasadit cibuli i cesnek
    array[pos] = 'C';
    pocet += vysazej_radek(array, pos + 1, N);
    array[pos] = '*';
    pocet += vysazej_radek(array, pos + 1, N);
  } else { // Jinak jsem nekde v radku
    if (array[pos - 1] == 'C') { // Kdyz je predchozi sazenicka cibule, muze byt dalsi sazenicka cibule i cesnek
      array[pos] = 'C';
      pocet += vysazej_radek(array, pos + 1, N);
      array[pos] = '*';
      pocet += vysazej_radek(array, pos + 1, N);            
    } else { // Jinak je predchozi sazenicka cesnek a dalsi sazenicka tak muze byt jenom cibule (nemuzou byt dva cesneky za sebou)
      array[pos] = 'C';
      pocet += vysazej_radek(array, pos + 1, N);      
    }
  }
  
  return pocet;
}

const int N = 5;

int main(int argc, char* argv[])
{
  char array[N];
  int pocet = vysazej_radek(array, 0, N);
  printf("Pocet moznosti: %d\n", pocet);

  return 0;
}

napsal sem ten program, ale dost nešikovně jsem začátečník. Bohuzel mi nefunguje použil jsem ten vaš nápad s tou binární soustavou a do cyklu while jsem vložil přičítání 1 k tomu poli cibulí. To přičítání jsem reazlizoval pomocí testů if, kde jsem napsal 6 možností (6 if-ů) které mohou nastat při sčítání binárních čísel. Cyklus while mi má běžet dokud se cibulovy zahon a cesnekovy zahon nerovnaji to znamená kdy oba budou obsahovat samý jedničky takže samý česneky jako je obsahuje česnekový zahon. Pak to skočí nakonec kde mi čítač vypíše počet možností (pokud nejsou vedle sebe cesneky(dve jednicky). Ve výsledku mi to dělá nekonečný cyklus a vypisuje to pořád jen samy nuly vubec to nepřičítá do toho pole jedničku nevíte prosím někdo kde mám chybu?

package algoritmy;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int [] zahon;
        int [] cibulZahon;
        int [] cesnekZahon;
        int [] pomocZahon;
        int [] prenosZahon;
        int i;
        int citac = 0;
        Scanner sc = new Scanner(System.in);

        System.out.println("Zadejte pocet sazenicek");
        int n = sc.nextInt();

        zahon = new int[n];
        cibulZahon =  new int[n];
        cesnekZahon = new int[n];
        pomocZahon =  new int[n];
        prenosZahon = new int[n+1];

        for( i=0 ; i < zahon.length; i++ ){
        cibulZahon[i] = 0;
        }

        for( i=0 ; i < zahon.length; i++ ){
        cesnekZahon[i] = 1;
        }

        for( i=0 ; i < zahon.length; i++ ){
        pomocZahon[i] = 1;
        }

        for( i=0 ; i <= zahon.length; i++ ){
        prenosZahon[i] = 0;
        }

        boolean v;
        while(v = (Arrays.equals(cibulZahon, cesnekZahon)) == false){

        for( i=0 ; i < zahon.length; i++ ){

        if(cibulZahon[i] == 0 && pomocZahon[i] == 0 && prenosZahon[i] == 0){        //1
        cibulZahon[i] = 0;
        }
       
        if(cibulZahon[i] == 1 && pomocZahon[i] == 0 && prenosZahon[i] == 0){        //2   
        cibulZahon[i] = 1;
        }
       
        if(cibulZahon[i] == 0 && pomocZahon[i] == 1 && prenosZahon[i] == 0){        //3   
        cibulZahon[i] = 1;
        }
       
        if(cibulZahon[i] == 0 && pomocZahon[i] == 0 && prenosZahon[i] == 1){        //4   
        cibulZahon[i] = 1;
        }
       
        if(cibulZahon[i] == 1 && pomocZahon[i] == 1 && prenosZahon[i] == 0){        //5   
        cibulZahon[i] = 0;
        prenosZahon[i+1] = 1;
        }
       
        if(cibulZahon[i] == 1 && pomocZahon[i] == 0 && prenosZahon[i] == 1){        //6 
        cibulZahon[i] = 0;
        prenosZahon[i+1] = 1;
        }
    }
        boolean vypis = true;
        int pred = 2;
       
        for( i=0 ; i < cibulZahon.length; i++ ){
        if(cibulZahon[i] == 1 && pred == 1){
        vypis = false;
        }
        pred = cibulZahon[i];
    }

        if(vypis == true){
        for( i=0 ; i < cibulZahon.length; i++ ){
        System.out.print(cibulZahon[i]);
        }
        System.out.println();
        citac = citac + 1;
        }

        }
        System.out.println(citac);
    }

}

omlouvam se pomocZahon ma byt ve tvaru 100000.... (na zacatku jednicka)

takze

for( i=0 ; i < zahon.length; i++ ){
        pomocZahon[i] = 0;
        }

pomocZahon[0] = 1;

Ono to programování od toho normálního života zase tak odtažené není, takže pokud máš sázet jeden řádek, tak ti opravdu stačí jedno pole.

Představ si, že uživatel zadá nějaké N. Ty vytvoříš pole o délce N + 1. Nejprve to pole celé vynuluješ - zasázíš cibuli (jen tak mimochodem je to první varianta). 

zahon = new int[n + 1];

for (int i = 0;i < (n + 1);i++) zahon[i] = 0;

Vstoupíš do cyklu - pro tento případ by se pěkně hodil s podmínkou na konci (do-while). V těle tohoto cyklu nejprve zkontroluješ, jestli je aktuální varianta platná, tj. opět cyklem (index I) projdeš pole od 0 do N - 1 a budeš koukat, jestli hodnota na I a I + 1 v poli je 1, a pokud ano, tak máš 2 česneky vedle sebe, a to "nelze". Po kontrole varianty si připravíš další.

do {
	// zde bude kontrola aktualniho radku

	// a jeho vypsani
	for (int i = 0;i < n;i++) {
		System.out.print("%d ", zahon[i]);
	}

Zjednodušeně řečeno - cibule je 0 a česnek je 1 - vezmeš číslo na indexu 0 a zvedneš ho o 1. Pokud bude rovno 1, tak máš další variantu, jinak (byla by tam dvojka) ji změníš na 0 a zvedneš hodnotu na indexu 1. Pokud je tam 1, tak máš další variantu, Pokud je tam 2, tak opět nuluješ (index 1) a jdeš na index 2. A takto až do indexu N + 1.

Celé se to dá realizovat jedním cyklem s daným počtem opakování, ve kterém bude nejprve inkrement na daném indexu, následně podmínka s případným break nebo v opačném případě vynulování hodnoty v poli na aktuálním indexu. 

	// dalsi varianta
	for (int i = 0;i < (n + 1);i++) {
		// je-li tam cibule
		if (zahon[i] == 0) {
			// tak zasad cesnek (dalsi varianta)
			zahon[i] = 1;
			break;
		}
		// jinak tam byl cesnek
		else {
			// takze tam zpatky vratime cibuli
			zahon[i] = 0;
			// cesnek se zasadi nekde dal v cyklu
		}
	}

A proč mít pole o délce N + 1? No protože hlavní cyklus (do-while) pojede dokud je hodnota v poli na tomto posledním přidaném indexu 0. Ve chvíli, kdy se tam objeví 1, tak si prošel všechny varianty a program může skončit. 

} while(zahon[n] == 0);

Místo testu správnosti varianty tam je "jenom" vypsání. Ale test je tam taky popsaný, tak se s tím zkus popasovat.