» »

python-pomoč pri nalogi z nizi

python-pomoč pri nalogi z nizi

ktka ::

Pozdravljeni!

Imam sledečo nalogo:
Napiši program , ki pove kolikokrat se en niz pojavi v drugem. Štejejo tudi nestrnjene pojavitve, torej je lahko med znaki enega niza tudi poljubno znakov drugega niza.
Primer:
Vnesi prvi niz: slastna banana
Vnesi drugi niz: ana
Niz 'ana' se v nizu 'slastna banana' pojavi 14 krat.

Kako naj se lotim naloge? Ne vem ali ima to kako zvezo z kombinatoriko?

Spura ::

Nima. Najlazje to resis z rekurzivno funkcijo.

ktka ::

Ja amapk ne znam programirat z rekurzivnimi funkcijami.

Mipe ::

Za vsak znak v drugem nizu preštej pojavitve v prvem nizu. Če se znak v drugem nizu pojavi, minus ena pojavitev za ta drugega. Ni treba neke rekurzije. Bo šlo?

Spura ::

Sori, ne stekam cist tega. Ce prestejem kolikokrat se znaki iz "ana" pojavijo v "slastna banana" dobim 5+3+5 kar je 13.
Ce prestejem kolikokrat se znaki iz "slastna banana" pojavijo v "ana" dobim 2 + 1 + 2 + 2 + 1 + 2 + 1 + 2 = 13.

ktka ::

sm tela prekopirat excelov dokument, pa ne rata:)

Randomness ::

Mipe, tudi jaz ne razumem tvoje rešitve. Jo lahko bolj preciziraš?
Tukaj pa je rešitev z rekurzijo (ne sicer v jeziku iz naslova). Upam, da nisem preveč pomagal.
package main

import "fmt"

func countSubstrings(a string, b string) int {
    if len(a) == 0 || len(b) == 0 {
        return 0
    }

    return doCountSubstrings(a, b, 0)
}

func doCountSubstrings(a string, b string, n int) int {
    if (len(b) == 0) {
        n++
    } else {
        for i := 0; i < len(a); i++ {
            if (a[i] == b[0]) {
                n = doCountSubstrings(a[i+1:], b[1:], n)
            }
        }
    }

    return n
}

func main() {
    s := "slastna banana"
    ss := "ana"

    fmt.Println(countSubstrings(s, ss))
}

Zgodovina sprememb…

galu ::

Iz drugega niza narediš array;
for loop, ki prečekira celoten prvi niz;
v loopu, pa se čekira če se for-ov index enači s katerim stringom iz arraya. Če se, dodaj neki spremenljivki vrednost 1;

Did I fail at something?

edit: Pardon, Pythonovi "Arrayi" se imenujejo liste.
Tako to gre.

Zgodovina sprememb…

  • spremenil: galu ()

Randomness ::

GaŁu, težko razumem na tak (ala Thomas) način podan postopek. Lahko mogoče prilepiš psevdo kodo?

Spura ::

Randomness a si pognal pa dela? Probi se "nslastna banana", mora ti vrnit isto stevilo, 14.

mallard ::

Randomnessova rešitev dela.

galu je izjavil:

Iz drugega niza narediš array;
for loop, ki prečekira celoten prvi niz;
v loopu, pa se čekira če se for-ov index enači s katerim stringom iz arraya. Če se, dodaj neki spremenljivki vrednost 1;

Did I fail at something?

edit: Pardon, Pythonovi "Arrayi" se imenujejo liste.


Pri jasnem izražanju, hehe. Tudi meni ni jasno...

Randomness ::

@Spura: Izvoli, lahko preizkusiš tudi sam. Link

Spura ::

Kul. Tezko dojet te indeks telovadbe.

Jst sm napisal v javi.

	private static int count(int idxIskani, int idxPodatek, String iskani, String podatek) {
		if (idxPodatek == podatek.length() || idxIskani == iskani.length()) {
			return 0;
		}
		int retCount = 0;
		if (iskani.charAt(idxIskani) == podatek.charAt(idxPodatek)) {
			if (idxIskani + 1 == iskani.length()) {
				// nasli enega
				retCount++;
			} else { // nasli en znak, napredujemo za en znak v obeh stringih
				retCount += count(idxIskani + 1, idxPodatek + 1, iskani, podatek);
			}
		}
		return retCount + count(idxIskani, idxPodatek + 1, iskani, podatek);
	}

galu ::

:D

1. Iz črk, katere sestavlja vnos (torej, drugi niz - "ana") narediš array.
2. Ko je array shranjen, se začne for loop, ki pregleda vsako črko v prvem nizu ("slastna banana").
V tem loopu pa je koda v smislu: Če se trenutna črka, ki jo for loop gleda, nahaja v prej shranjenem arrayu, se k neki spremenljivki (i.e. 'result') prišteje vrednost ena (result += 1).
Na koncu for loopa se izpiše vrednost spremenljivke 'result'.

Je zej mal bolj jasno?:P
Tako to gre.

Spura ::

To ni niti pod razno pravilno.

Iscem:

"abc" v nizu "cbacba". Pravilen rezultat je 0 pojavitev, tvoj algoritem ne bo vrnil 0.

Mipe ::

Glej, ti iščeš strnjene pojavitve, ona pa nestrnjene.

Spura ::

Ne razumete. Vrstni red znakov je pomemben. V primeru ki sem ga dal ni niti ene nestrnjene pojavitve. In ne mores tega resit tako da bos po celem nizu iskal znake iskanega niza, ker te zjebe vrstni red. Sej si videl da dobis napacen rezultat na primeru ki je bil podan v OP.

mallard ::

@Mipe
slastna banana
||*||**|||||||
||*||*|||*||||
||*||*|||||*||
||*||*|||||||*
||*|||||||**||
||*|||||||*||*
||*|||||||||**
||||||*|||**||
||||||*|||*||*
||||||*|||||**
|||||||||***||
|||||||||**||*
|||||||||*||**
|||||||||||***
14

Zgodovina sprememb…

  • spremenilo: mallard ()

galu ::

Kolikor sem jaz razumel nalogo, se gre gre za nestrnjene pojavitve "niza"...:|
Tako to gre.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C#] Domača naloga - osnove

Oddelek: Programiranje
372328 (1545) 11tomi12
»

Rekurzija v javi z ArrayList

Oddelek: Programiranje
81447 (1290) marjan_h
»

Naloga v C-ju pomoč

Oddelek: Programiranje
112275 (1875) keworkian
»

[JavaScript] Sortiranje šumnikov

Oddelek: Programiranje
151988 (1722) MarkookraM
»

[C] Narascajoce sortiranje linearnega seznama

Oddelek: Programiranje
71757 (1646) Jebiveter

Več podobnih tem