Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Java zadatak sa stringom

[es] :: Java :: Java zadatak sa stringom

Strane: 1 2

[ Pregleda: 6188 | Odgovora: 24 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.isp.telekom.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Java zadatak sa stringom18.09.2014. u 18:07 - pre 115 meseci
Zdravo svima.

Radim jedan zadatak i naisao sam na ozbiljan problem. Nadam se da svi razumete engleski ali ako je potrebno mogu i da ga prevedem. Naime zadatak glasi ovako:

We have two strings A and B with the same super set of characters. We need to change these strings to obtain two equal strings. In each move we can perform one of the following operations:

1- swap two consecutive characters of a string
2- swap the first and the last characters of a string


A move can be performed on either string.
What is the minimum number of moves that we need in order to obtain two equal strings?
Input Format and Constraints:
The first and the second line of the input contains two strings A and B. It is guaranteed that the superset their characters are equal.
1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'


Output Format:
Print the minimum number of moves to the only line of the output



Sample input:
aab
baa


Sample output:
1


Explanation:
Swap the first and last character of the string aab to convert it to baa. The two strings are now equal.

Ono sto sam ja razmisljao jeste da se verovatno radi o dinamickom programiranju i sve ideje koje sam do sada imao nisu ni vredne pomena. Takodje, ja radim na nekoj ideji i resavanju tako da ako se desi da pre odgovora odradim ovaj zadatak, postavicu ga da bi i ostali znali.

P.S. Svaka sugestija, ideja je dobrodosla. Ne mora da bude resenje.

Hvala.
Dusan Punosevac
 
Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.isp.telekom.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Re: Java zadatak sa stringom21.09.2014. u 16:24 - pre 115 meseci
Ovo je neka moja najbolja ideja do sada, ali ipak ne vraca minimum pomeranja... Evo koda ako ista znaci:

Code:
package com.taskMinimumStringMoves;

import java.util.Scanner;

public class MinimumStringMoves {

    public static void swap(char aChar, char bChar) {
        char cChar;
        cChar = aChar;
        aChar = bChar;
        bChar = cChar;
    }

    public static void main(String[] args) {
        int moves = 0;
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the string A:");
        while (!scanner.hasNext("[A-Za-z]+")) {
            System.out
                    .println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
                            + "Enter your string A again!");
            scanner.nextLine();
        }
        String a = scanner.nextLine();
        a.toLowerCase();
        System.out.println("Enter the string B:");
        while (!scanner.hasNext("[A-Za-z]+")) {
            System.out
                    .println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
                            + "Enter your string B again!");
            scanner.nextLine();
        }
        String b = scanner.nextLine();
        b.toLowerCase();
        scanner.close();
        char[] aChar = a.toCharArray();
        char[] bChar = b.toCharArray();
        if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
            if (aChar[0] != bChar[0]) {
                if (aChar[0] == bChar[bChar.length - 1]) {
                    swap(bChar[0], bChar[bChar.length - 1]);
                    moves++;
                } else if (bChar[0] == aChar[aChar.length - 1]) {
                    swap(aChar[0], aChar[bChar.length - 1]);
                    moves++;
                }
            }
            for (int i = 0; i < aChar.length; i++) {
                if (aChar[i] == bChar[i]) {
                    continue;
                }
                for (int j = i + 1; j < aChar.length; j++) {
                    if (aChar[i] == bChar[j]) {
                        for (int k = j; k > i; k--) {
                            swap(bChar[k], bChar[k - 1]);
                            moves++;
                        }
                        break;
                    } else if (bChar[i] == aChar[j]) {
                        for (int k = j; k > i; k--) {
                            swap(aChar[k], aChar[k - 1]);
                            moves++;
                        }
                        break;
                    }
                }
                if (aChar == bChar) {
                    break;
                }
            }
            System.out.println("Minimum moves: " + moves);
        }
    }
}

Dusan Punosevac
 
Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.



+30 Profil

icon Re: Java zadatak sa stringom24.09.2014. u 03:04 - pre 115 meseci
Pročitao sam pitanje i odmah su mi pale na pamet dvije stvari. Možda ti pomognu, a možda ne. Simpatičan je problem, tako da ću vjerovatno ovih dana ozbiljnije razmisliti o njemu pa ću se javiti.

1. Predstavi stringove kao permutacije karaktera. Sjećam se da sam na fakultetu izučavao neki poznati algoritam za generisanje permutacija, koji je radio baš po principu zamjene mjesta. Nekako numerišeš permutacije, pa vidiš šta možeš da uradiš.

2. Pogledaj algoritam A*. Nekada davno sam preko njega rješavao problem pronalaska minimalnog broja koraka za rješavanje 8 puzzle problema, koji je nekako srodan problemu koji si ti izložio.
 
Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.isp.telekom.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Re: Java zadatak sa stringom24.09.2014. u 12:47 - pre 115 meseci
Uradio sam nesto ovako, medjutim i dalje nije jos to to. Mislim da moram da uracunam da vidi da li je to 1 pomeranje,2 ili 3, itd.

Code:
char[] aChar = a.toCharArray();
        char[] bChar = b.toCharArray();
        char cChar;
        if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
            if (aChar != bChar) {
                for (int i = 0; i < aChar.length; i++) {
                    for (int j = i + 1; j < aChar.length; j++) {
                        if (aChar[i] != bChar[i]) {
                            if (aChar[j] == bChar[i] && j < aChar.length) {
                                cChar = aChar[j];
                                aChar[j] = aChar[i];
                                aChar[i] = cChar;
                                moves++;
                            } else if (aChar[aChar.length - 1] == bChar[i]) {
                                cChar = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = aChar[i];
                                aChar[i] = cChar;
                                moves++;
                            } else {
                                if (aChar[j] != aChar[i] && j < aChar.length) {
                                    if (aChar[j] == bChar[j]) {
                                        cChar = bChar[j];
                                        bChar[j] = bChar[i];
                                        bChar[i] = cChar;
                                        moves++;
                                    }
                                    cChar = aChar[j];
                                    aChar[j] = aChar[i];
                                    aChar[i] = cChar;
                                    moves++;
                                } else if (bChar[j] != bChar[i]
                                        && i + 1 < aChar.length) {
                                    if (aChar[j] == bChar[j]
                                            && aChar[j] != aChar[i]) {
                                        cChar = aChar[j];
                                        aChar[j] = aChar[i];
                                        aChar[i] = cChar;
                                        moves++;
                                    }
                                    cChar = bChar[j];
                                    bChar[j] = bChar[i];
                                    bChar[i] = cChar;
                                    moves++;
                                }
                            }
                            if (aChar == bChar) {
                                break;
                            }
                        }
                    }
                }
            }
            System.out.println("Minimum number of moves: " + moves);
        }

Dusan Punosevac
 
Odgovor na temu

river
System Architect

Član broj: 12566
Poruke: 62
*.com
Via: [es] mailing liste



+1 Profil

icon Re: Java zadatak sa stringom24.09.2014. u 13:13 - pre 115 meseci
Pozdrav,

Ukoliko se ne varam - postavka problema upucuje na jedan poznat algoritam: https://en.wikipedia.org/wiki/Levenshtein_distance .
Everything should be made as simple as possible, but not simpler. - AA
 
Odgovor na temu

river
System Architect

Član broj: 12566
Poruke: 62
*.com
Via: [es] mailing liste



+1 Profil

icon Re: Java zadatak sa stringom24.09.2014. u 13:17 - pre 115 meseci
Ispravka, samo je na prvi pogled izgledalo kao Levenstajnova distanca, ali mozda ti slican algoritam da ideju kako da nastavis.

Pozdrav
Everything should be made as simple as possible, but not simpler. - AA
 
Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.



+30 Profil

icon Re: Java zadatak sa stringom25.09.2014. u 14:10 - pre 115 meseci
Neću ti pisati implementaciju algoritma, ali ću ti opisati algoritam koji rješava ovaj problem.
Naime problem možeš riješiti algoritmom A*. A* je verzija Dijestrinog algoritma za pronalazak najkraćeg puta izmedju dva čvora u grafu. Ti graf nećeš eksplicitno praviti, ali možeš posmatrati problem kao grafovski. Naime treba da dodješ od početnog čvora (prva riječ) do krajnjeg čvora (druga riječ). Iz svakog čvora možeš doći u nekog njegovog sina, kojih ima n, gdje je n veličina riječi. Sinove nekog čvora formiraš tako što zamjeniš dva susjedna slova. Tako npr. od čvora 1234, dobijaš sinove 2134,1324,1243 i 4231, jer osim susjednih slova, možeš mjenjati i prvo i poslednje, ako sam ja dobro razumio zadatak. Svakom generisanom sinu x dodjeljuješ neku vrijednost, f(x) = g(x) + h(x), gdje je g(x) cijena puta od polaznog čvora do čvora x (broj koraka/zamjena da se dodje od početnog čvora do čvora x), a h(x) je heuristička funkcija. Poenta ovog algoritma je u h(x). Heuristika je neka procjena. Naime, trebaš svakom čvoru da dodjeliš vrijednost "koliko je on udaljen od rešenja". Tako npr heuristika može da bude koliko slova nije na svom mjestu: Ako imamo čvor x=1243, a ciljani čvor je 1234, tada je h(x)=2 jer dva elementa: 3 i 4, nisu na svom mjestu. Naravno, heuristike mogu biti dobre i loše, to je na tebi da smisliš. Sada smo izračunali f(x) za svako dijete od trenutno posmatranog čvora. U sledećem koraku biramo ono dijete kome je f(x) najmanje. U jednom trenutku ćeš doći do ciljanog čvora, što je logično, jer ćeš da izlistaš sve permutacije. Ako je heuristička funkcija "admisible" (ne precjenjuje optimalno rešenje), onda ti ovaj algoritam nalazi najkraći put od početnog do krajnjeg čvora, odnosno najmanji broj koraka da transformišeš prvu riječ u drugu. Što je heuristika bolja, to algoritam radi brže. Kada je heuristička funkcija "admisible" i kada je "bolja" možeš pročitatu u priloženim linkovima.

http://en.wikipedia.org/wiki/A*_search_algorithm
http://en.wikipedia.org/wiki/Heuristic_function
http://feynmanliang.com/comparing-astar-heuristics/

Javi se ako ti nešto nije jasno ili ako ti bude potrebna dodatna pomoć. Mogu ti ovo implementirati u Javi, ali mislim da je poenta u tome da to uradiš sam.
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Java zadatak sa stringom25.09.2014. u 14:18 - pre 115 meseci
Pa napiši čoveku algoritam !
Evo baš bih voleo da vidim @blekmor implementaciju (nije bitan jezik).
 
Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.



+30 Profil

icon Re: Java zadatak sa stringom25.09.2014. u 14:51 - pre 115 meseci
Algoritam je opisan u detalje u mom prethodnom postu. To što ga ti ne znaš protumačiti je tvoj problem. Pored toga su ostavljeni linkovi za dodatne informacije. Implementacija nije napisana, jer je korisnik koji je postavio pitanje student (piše u opisu) i tražio je ideju ili sugestiju. U svojoj prvoj poruci sam mu dao sugestiju da koristi A*, ali ga izgleda nisam dovoljno zainteresovao, pa sam odlučio da mu detaljnije objasnim kako se problem može rješiti korištenjem A* algoritma. Moja namjera je da pomognem momku, a mislim da je ova vrsta pomoći bolja, nego da mu tutnem kod koji vjerovatno neće ni razumiti iz prve. Meni je puno lakše da napišem rješenje u 10ak linija koda nego da objašnjavam suštinu, kao što pokušavam. Ako bude htio da mu napišem implementaciju, biću rad da to uradim.
 
Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.isp.telekom.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Re: Java zadatak sa stringom25.09.2014. u 20:33 - pre 115 meseci
@blekmor Hvala na pomoci i ideji. Ali imam jedno pitanje. Sve kako si objasnio mi je savrseno jasno, ali ja nemam zapravo cilj. Ako imam string perapare i parepera, jedini cilj koji imam je da oni budu jednaki. A da li ce biti na kraju parepare ili perapera ili pak praeprae totalno je nebitno. Samo je bitan broj minimalnih pomeranja.
Da li je onda bez obzira na ovu gore pomenutu cinjenicu primenjiv ovaj algoritam? Inace, totalno je u redu da mi ne das implementaciju. Ovo mi treba da uradim i shvatim. Ideje sam vec pokupio, gomila i probacu nesto. U slucaju da bas ne budem mogao da resim potrazicu kod. U svakom slucaju hvala!

Pozdrav!
Dusan Punosevac
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Java zadatak sa stringom25.09.2014. u 20:40 - pre 115 meseci
u prevodu, napiši čoveku algoritam, naravno, ako znaš.
 
Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.



+30 Profil

icon Re: Java zadatak sa stringom25.09.2014. u 22:32 - pre 115 meseci
Ako transformišeš prvi string i dobiješ neki "medju-string", a paraleno transformišeš drugi string, i dobiješ taj isti "medju-string", biće ti potreban isti broj koraka kao kad transformišeš prvi string do tog "medju-stringa", i onda "medju-string" transformišeš do drugog stringa. To važi zato što je minimalan broj koraka da string A transformisao u string B jednak minimalnom broju koraka potrebnih za transformaciju stringa B u string A. Naravno, redoslijed koraka je obrnut, ali tebe to ne zanima, tebe zanima samo broj koraka. Znači da je algoritam primenljiv.
Javi kako napreduješ i ako ti bude trebala dodatna pomoć.

@galaksija
Algoritam sam mu napisao i objasnio. Sad da li ti mene troluješ, ili jednostavno ne znaš razliku izmedju algoritma i implementacije algoritma, to ne mogu da procjenim. Nadam se da je u pitanju ovo prvo. U tom slučaju sam se primio, i čestitam ti.(smajli) Pored toga sam već objasnio zašto nisam ovde napisao implementaciju algoritma koji rješava postavljeni problem, i o tome više neću pisati. Naravno, tebi mogu poslati implementaciju u privatnoj poruci, ukoliko to želiš, ali tu nema ništa zanimljivo; algoritam je jasan i implementacija je straightforward.
 
Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.sbb.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Re: Java zadatak sa stringom13.10.2014. u 09:08 - pre 115 meseci
Pozdrav svima. Izvinite zbog zakasnelog odgovora, ali evo da vam izbacim moje resenje:

Code:
    public int findMinimumStringMovement() {
        int moves = 0;
        char[] aChar = a.toCharArray();
        char[] bChar = b.toCharArray();
        char cChar;

        if (aChar != bChar) {
            for (int i = 0; i < aChar.length; i++) {
                for (int j = i + 1; j < aChar.length; j++) {
                    if (aChar[i] != bChar[i]) {
                        /*
                         * It checks if some character from the array of aChar
                         * is same as other character from the array of B and if
                         * it's j less then the length of the array. If it's
                         * true, then swap the characters and count moves
                         */
                        if (aChar[j] == bChar[i] && j < aChar.length) {
                            for (int k = j; k > i; k--) {
                                cChar = aChar[k];
                                aChar[k] = aChar[k - 1];
                                aChar[k - 1] = cChar;
                                moves++;
                            }
                            /*
                             * In other case, if the last character of array
                             * aChar same as the some character of bChar and
                             * vice versa, then we should check if the i is
                             * equal to 0, in that case we swap 1st and last
                             * character of array and count as 1 move else if i
                             * value is less then the value of length of array
                             * divided with 2 then it swaps that character to
                             * the first one and then swaps with last and counts
                             * the moves.
                             */
                        } else if (aChar[aChar.length - 1] == bChar[i]) {
                            if (i == 0) {
                                cChar = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = aChar[i];
                                aChar[i] = cChar;
                                moves++;
                            } else if (i < (aChar.length - 1) / 2) {
                                for (int k = i; k > 0; k--) {
                                    cChar = aChar[k];
                                    aChar[k] = aChar[k - 1];
                                    aChar[k - 1] = cChar;
                                    moves++;
                                }
                                cChar = aChar[i];
                                aChar[i] = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = cChar;
                            }
                        } else if (bChar[bChar.length - 1] == aChar[i]) {
                            if (i == 0) {
                                cChar = bChar[bChar.length - 1];
                                bChar[bChar.length - 1] = bChar[i];
                                bChar[i] = cChar;
                                moves++;
                            } else if (i < (aChar.length - 1) / 2) {
                                for (int k = i; k > 0; k--) {
                                    cChar = aChar[k];
                                    aChar[k] = aChar[k - 1];
                                    aChar[k - 1] = cChar;
                                    moves++;
                                }
                                cChar = aChar[i];
                                aChar[i] = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = cChar;
                            }
                            /*
                             * And the last case is if there is no other option,
                             * then we asks if some characters in array with
                             * positions i and j are different and if the j
                             * value is less then length of the array and do the
                             * swap.
                             */
                        } else {
                            if (aChar[j] != aChar[i] && j < aChar.length) {
                                if (aChar[j] == bChar[j]) {
                                    cChar = bChar[j];
                                    bChar[j] = bChar[i];
                                    bChar[i] = cChar;
                                    moves++;
                                }
                                cChar = aChar[j];
                                aChar[j] = aChar[i];
                                aChar[i] = cChar;
                                moves++;
                            } else if (bChar[j] != bChar[i] && j < aChar.length) {
                                if (aChar[j] == bChar[j]
                                        && aChar[j] != aChar[i]) {
                                    cChar = aChar[j];
                                    aChar[j] = aChar[i];
                                    aChar[i] = cChar;
                                    moves++;
                                }
                                cChar = bChar[j];
                                bChar[j] = bChar[i];
                                bChar[i] = cChar;
                                moves++;
                            }
                        }
                        /*
                         * At the end, if arrays are equal, then it is done.
                         */
                        if (aChar == bChar) {
                            break;
                        }
                    }
                }
            }
        }
        return moves;
    }


Nadam se da vam je pomoglo.
Pozdrav.
Dusan Punosevac
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Java zadatak sa stringom13.10.2014. u 11:31 - pre 115 meseci
Pa, nije nam pomoglo iz više razloga. Možda je najvažniji taj što nismo ni imali problem, a ne manje važno je i to što tvoj program ne radi dobro.

Ajde, pusti kroz tvoj program da se nađe rešenje za stringove:

abcdefghijklmnopqrstuvwxyz
bzcdefghijklmnopqrstuvwxay

Rešenje je 3:
1. zameni mesta bz, dobije se zbcdefghijklmnopqrstuvwxay
2. zameni mesta ay, dobije se zbcdefghijklmnopqrstuvwxya
3. zameni mesta z i a, dobije se abcdefghijklmnopqrstuvwxyz, što je i trebalo da se dobije.

blekmor te je lepo uputio na rešenje, a ti nisi ni blizu...
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Java zadatak sa stringom13.10.2014. u 11:45 - pre 115 meseci
Uzgred, evo jednog algoritma koji radi slično kao ovo što si ti napisao, ali ne daje optimalan broj pomeranja:

Uradi bubble sort nad prvim stringom i zapamti broj zamena z1.
Uradi bubble sort nad drugim stringom i zapamti broj zamena z2.
Ako su sada stringovi isti, onda je ukupan broj zamena Z=z1+z2.
Naravno, ovo nije optimalno, ali ti daje neku procenu:
1. kaže ti koja je GORNJA granica broja zamena (tj. dubinu pretrage posle koje treba da obustaviš pretraživanje)
2. kaže ti da li je uopšte MOGUĆE da od stringa2 napraviš string1.
 
Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.sbb.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Re: Java zadatak sa stringom13.10.2014. u 12:39 - pre 115 meseci
@djoka_I interesantna stvar je ta sto meni vraca 3 promene... Nakon blizeg pogleda video sam da sam lose prekopirao kod. Imao sam duplikat istog, ali sam dao pogresan. Ovo je pravi, i uradjen je na istu foru i vraca dobar broj pomeranja. Evo koda:


Code:
public int findMinimumStringMovement() {
        int moves = 0;
        char[] aChar = a.toCharArray();
        char[] bChar = b.toCharArray();
        char cChar;

        if (aChar != bChar) {
            for (int i = 0; i < aChar.length; i++) {
                for (int j = i + 1; j < aChar.length; j++) {
                    if (aChar[i] != bChar[i]) {
                        /*
                         * It checks if some character from the array of aChar
                         * is same as other character from the array of B and if
                         * it's j less then the length of the array. If it's
                         * true, then swap the characters and count moves
                         */
                        if (aChar[j] == bChar[i] && j < aChar.length) {
                            for (int k = j; k > i; k--) {
                                cChar = aChar[k];
                                aChar[k] = aChar[k - 1];
                                aChar[k - 1] = cChar;
                                moves++;
                            }
                            /*
                             * In other case, if the last character of array
                             * aChar same as the some character of bChar and
                             * vice versa, then we should check if the i is
                             * equal to 0, in that case we swap 1st and last
                             * character of array and count as 1 move else if i
                             * value is less then the value of length of array
                             * divided with 2 then it swaps that character to
                             * the first one and then swaps with last and counts
                             * the moves.
                             */
                        } else if (aChar[aChar.length - 1] == bChar[i]) {
                            if (i == 0) {
                                cChar = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = aChar[i];
                                aChar[i] = cChar;
                                moves++;
                            } else if (i < (aChar.length - 1) / 2) {
                                for (int k = i; k > 0; k--) {
                                    cChar = aChar[k];
                                    aChar[k] = aChar[k - 1];
                                    aChar[k - 1] = cChar;
                                    moves++;
                                }
                                cChar = aChar[i];
                                aChar[i] = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = cChar;
                            }
                        } else if (bChar[bChar.length - 1] == aChar[i]) {
                            if (i == 0) {
                                cChar = bChar[bChar.length - 1];
                                bChar[bChar.length - 1] = bChar[i];
                                bChar[i] = cChar;
                                moves++;
                            } else if (i < (aChar.length - 1) / 2) {
                                for (int k = i; k > 0; k--) {
                                    cChar = aChar[k];
                                    aChar[k] = aChar[k - 1];
                                    aChar[k - 1] = cChar;
                                    moves++;
                                }
                                cChar = aChar[i];
                                aChar[i] = aChar[aChar.length - 1];
                                aChar[aChar.length - 1] = cChar;
                                moves++;
                            }
                            /*
                             * And the last case is if there is no other option,
                             * then we asks if some characters in array with
                             * positions i and j are different and if the j
                             * value is less then length of the array and do the
                             * swap.
                             */
                        } else {
                            if (aChar[j] != aChar[i] && j < aChar.length) {
                                if (aChar[j] == bChar[j]) {
                                    cChar = bChar[j];
                                    bChar[j] = bChar[i];
                                    bChar[i] = cChar;
                                    moves++;
                                }
                                cChar = aChar[j];
                                aChar[j] = aChar[i];
                                aChar[i] = cChar;
                                moves++;
                            } else if (bChar[j] != bChar[i] && j < aChar.length) {
                                if (aChar[j] == bChar[j]
                                        && aChar[j] != aChar[i]) {
                                    cChar = aChar[j];
                                    aChar[j] = aChar[i];
                                    aChar[i] = cChar;
                                    moves++;
                                }
                                cChar = bChar[j];
                                bChar[j] = bChar[i];
                                bChar[i] = cChar;
                                moves++;
                            }
                        }
                        /*
                         * At the end, if arrays are equal, then it is done.
                         */
                        if (aChar == bChar) {
                            break;
                        }
                    }
                }
            }
        }
        return moves;
    }
}


Zaboravio sam u prethodonom kodu da mi je falio jedan brojac pomeranja.

P.S. Ne znam cemu tolika potenciranja nekih algoritama. 100 ljudi, 100 cudi. Ne mora sve da se radi po sablonu koji je neko vec radio.

Pozdrav.
Dusan Punosevac
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Java zadatak sa stringom13.10.2014. u 13:33 - pre 115 meseci
Za stringove "abcdeaaa", "abccccaaaaa" daje rezultat 9.
Da li možeš da objasniš kako se u 9 koraka stiže do identičnih stringova?
 
Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.sbb.rs.

Sajt: rs.linkedin.com/in/dpunos..


+5 Profil

icon Re: Java zadatak sa stringom13.10.2014. u 14:01 - pre 115 meseci
@djoka_I pa vrlo jednostavno. Ako procitas zadatak, videces uslove koji kazu sledece:
Citat:

Input Format and Constraints:
The first and the second line of the input contains two strings A and B. It is guaranteed that the superset their characters are equal.
1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'


Kada ovo procitas shvatices da je to sto si ti napisao nedopustiv unos, kao i da je tvoja pojava vrlo lako kontrolisana i resiva kodom koji mi se nalazi u main metodi:

Code:
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the string A:");
        while (!scanner.hasNext("[A-Za-z]+")) {
            System.out
                    .println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
                            + "Enter your string A again!");
            scanner.nextLine();
        }
        String a = scanner.nextLine();
        a.toLowerCase();
        System.out.println("Enter the string B:");
        while (!scanner.hasNext("[A-Za-z]+")) {
            System.out
                    .println("Nope, that's not it! Enter the value from \"a\" to \"z\"."
                            + "Enter your string B again!");
            scanner.nextLine();
        }
        String b = scanner.nextLine();
        b.toLowerCase();
        scanner.close();
        if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) {
            MinimumStringMoves minimumStringMoves = new MinimumStringMoves(a, b);
            System.out.println("Minimum string moves: "
                    + minimumStringMoves.findMinimumStringMovement());
        }
    }


Tako da to sto si ti napisao bi prijavilo gresku i ne bi dozvolilo obradu programa.
Pozdrav.
Dusan Punosevac
 
Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.



+30 Profil

icon Re: Java zadatak sa stringom14.10.2014. u 01:00 - pre 115 meseci
@olp29
Da li si siguran da ovo rješenje daje zaista najmanji mogući broj koraka? Pogledao sam tvoj metod i nije mi jasno na osnovu čega to možeš da tvrdiš? Jedini korektan odgovor na ovo pitanje je dokaz valjanosti algoritma. Naravno, ne tražim od tebe da mi išta dokazuješ, nego ti skrećem pažnju da jedino uz dokaz možeš biti siguran da ti je rješenje tačno. Možda izgleda kao tačno, ali "izgleda" nije dovoljan argument.

Prekopirao sam tvoj metod i zadao ulazne parametre "abababab" i "aaaabbbb" i tvoj metod kaže da je potrebno 9 koraka. Medjutim, postoji rešenje u 4 koraka:
abababab -> baababab -> baababba -> aaababbb ->aaaabbbb,
što znači ili da tvoje rješenje nije tačno ili da ja nisam dobro prekopirao rješenje (dva puta sam kopirao, isti su mi rezultati) ili da ti nisi dobro kopirao rješenje na forum.

Možda griješim, ali čini mi se da ti je pristup loš.

Citat:
olp29:
P.S. Ne znam cemu tolika potenciranja nekih algoritama. 100 ljudi, 100 cudi. Ne mora sve da se radi po sablonu koji je neko vec radio.

Naravno da ne mora. Ne moraš putovati u susjedni grad vozom, tom čudnom aždajom, ako ti neko to predloži. Možeš krenuti hodajući nogama ili rukama. Možeš možda napraviti mašinu za teleport, ili nešto slično. Ali jednom kada odeš vozom, sledeći put ćeš znati kako da prilično efikasno odeš do susjednog grada, bez mnogo razmišljanja. To ne znači da svugdje možeš i trebaš ići vozom (jako mnogo volim vozove), ali da ga uvjek treba imati na umu i znati procjeniti kada ga iskoristiti. Sa druge strane, opterećivanje šablonima uništava kreativnost, tako da treba znati balansirati.

Konkretno, dobio sam ideju kako da rješim problem koji si postavio nakon nekoliko minuta razmišljanja. Nakon toga mi je bilo potrebno još 10ak minuta kako bih u potpunosti rješio problem (bez implementacije). Sa druge strane ti se mučiš sa problemom prilično dugo. To ne znači da sam ja pametniji od tebe. To znači da sam se ja već vozio vozom na toj relaciji i znam gdje je stanica, dok si ti odmah krenuo hodajući, i to, čini mi se, na rukama.

"štuj one koji bili su tu pre tebe, da nije bilo njih, ne bi bilo ni tebe" - Furio Djunta (smajli)

Pozdrav
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Java zadatak sa stringom14.10.2014. u 09:13 - pre 115 meseci
Evo i ja da ti predložim kako da testiraš program da bi bio siguran da daje optimalan broj poteza.

Pošto si mi skrenuo pažnju da su ograničenja da su nizovi sastavljeni tako da uvek postoji rešenje, možeš Monte Karlo metodom da uradiš sledeću seriju testova:

1. Generiši slučajan niz znakova dužine n (1 < n < 2000)
2. Generiši slučajan broj m u nekom opsegu recimo (5 < m < 100)
3. Za svako k = 1..m
4.a uradi k slučajnih transformacija nad nizom (zamena mesta susednim članovima, ili prvog i poslednjeg)
5.a nađi broj poteza koji tvoj algoritam vraća.
6.a ako je broj poteza koji je tvoj program pronašao manji ili jednak od k onda je eksperiment uspešan.
7.a ako nije, ispiši početni i krajnji string, da bi kasnije mogao da analiziraš zašto nije nađen najkraći broj koraka

Sve ovo ponavljaj dokle god se za svaki slučajni niz i za svaki broj slučajnih transformacija ne dobije da program nalazi rešenje za manji ili jednak broj koraka u odnosu na broj slučajnih koraka.

Tek nakon nekoliko hiljada eksperimenata možeš da se nadaš da tvoj progrom stvarno možda radi kako treba.

 
Odgovor na temu

[es] :: Java :: Java zadatak sa stringom

Strane: 1 2

[ Pregleda: 6188 | Odgovora: 24 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.