Ile razy występuje dany podciąg

0

Mam problem z tym zadaniem. x;

http://wklej.to/MOtIq

user image

Jak to naprawić?

0

ale pokombinowales, na pierwszy rzut oka to te offsety sa zle, t.j. 6 czy 7

2

Po co wklejasz konsolę, która nie ma nic wspólnego z kodem? W tym kodzie nigdzie nie ma wypisywania Wspolnych liczb tego podciagu....

Opowiedz słowami, co chcesz zrobić, bo ten kod robi jakieś dziwne cyrki. No i oczywiście warunki pętli są złe.

1

szukalem jakiegos fajnego rozwiazania z count_if ale nie moglem nic wymyslec.
Opisze Ci jak to zrobic

Zaczales dobrze z podtablica. Jednak ja bym uzyl w tym zadaniu std::list (ze wzgledu na usuwanie elementow)

Wiec masz jakies wejscie.

  1. szukasz pierwszego elementu za pomoca tej funkcji
    http://www.cplusplus.com/reference/algorithm/find/

  2. jezeli znajdziesz ten element to wywolujesz funkcje
    http://www.cplusplus.com/reference/algorithm/equal/
    na takiej zasadzie

auto myListIterator = tuZmiennaKtoraZostalaWywolanaZFunkcjaFind;
if ( std::equal (myListIterator , myListIterator + podTablica.Length() - 1, podTablica.begin())) 
  1. jezeli tak, to usuwasz N liczb z Listyliczb gdzie n to jest podTablica.Length() oraz zwiekszasz licznik. Pozycja startowa to tuZmiennaKtoraZostalaWywolanaZFunkcjaFind
  2. jezeli nie, to w tej kolekcji juz nie ma wiecej par
  1. Robisz nad tym wszystkim petle dopoki find zwroci poprawny wynik
6

Zadanie wydaje mi się jasne, a wasze wątpliwości powodują że i ja wątpię.

Dany jest ciąg n-elementowy liczb całkowitych. Sprawdź, ile razy występuje w nim podciąg 10, 17 i 21

Ja to rozumiem dosłownie: w podanym ciągu {10, 17, 21, 17, 6, 10, 21, 17, 10} podciąg {10, 17, 21} występuje raz: na samym początku.
Dziwne wydają mi się pytania o spójność czy rozłączność, chyba że czegoś nie rozumiem a słowo „podciąg” ma tu jakieś specjalistyczne dziwne znaczenie.

W każdym razie.

Jaki kontener w C++ ma gotową funkcję wyszukiwania podciągu?

.
.
.
no? ;-)

#include <string>
#include <iostream>

using namespace std;

int main()
{
	basic_string<int> a = { 10, 17, 21 };
	basic_string<int> b = { 10, 17, 21, 17, 6, 10, 21, 17, 10 };

	size_t idx = 0;

	int found = 0;
	while (idx < b.size())
	{
		int pos = b.find(a, idx);
		if (pos == -1)
			break;
		
		found++;
		idx = pos + a.size();
	}	

	cout << found << endl;
	return 0;
}
3

W informatyce i w matematyce podciąg nie musi być spójny (jednokawałkowy). Jeśli jest wymagana spójność, to się to wyraźnie formułuje.
http://www.oi.edu.pl/l/zadania_rozgrzewkowe/ (zadanie 5), http://www.matematyka.pl/381178.htm, https://pl.wikipedia.org/wiki/Podci%C4%85g_%28matematyka%29. W podanym ciągu {10, 17, 21, 17, 6, 10, 21, 17,10} podciąg {10, 17, 21} występuje trzy razy.

0

To trzeba zrobić rekurencyjnie, ergo zapomnij o pakowaniu wszystkiego do main.

0

Mnie się jeszcze urodziło coś takiego:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void liczPodciagi(vector<int> podciag, vector<int> ciagGlowny) {
	static unsigned ilosc = 0;
	vector<int>::iterator it = search(ciagGlowny.begin(), ciagGlowny.end(), podciag.begin(), podciag.end());
	if (it != ciagGlowny.end()) {
		ilosc += 1;
		ciagGlowny.erase(it, it + 3);
		liczPodciagi(podciag, ciagGlowny);
	}
	else cout << ilosc << endl;
}

int main() {
	vector<int> a = { 10, 17, 21 };
	vector<int> b = { 4, 6, 10, 17, 21, 9, 4, 6 };

	liczPodciagi(a, b);
	return 0;
}

Liczenie rekurencyjne drogą eliminacji wystąpnień :) O_o

1 użytkowników online, w tym zalogowanych: 0, gości: 1