• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

wszystkie możliwe kombinacje liter C++ (poprawa kodu i inne sposoby)

Ultraszybki serwer VPS NVMe START
+1 głos
295 wizyt
pytanie zadane 13 września w C i C++ przez Jakub 0 Mądrala (5,600 p.)

Hej, napisałem prosty program dokonujący kombinacji na literach ,po prostu wpisze wszystkie możliwe ich ułożenia dzięki czemu powstaną też sensowne wyrazy . Program jest bardzo ograniczony i wypisuje tylko 4 literowe wyrazy z użyciem wielkich liter. Oczywiście potrafię to rozwinąć o większe możliwości ale zanim to zrobię muszę zadbać nieco o kod :) Oto on:

#include "stdafx.h" //Napisane w VS

using namespace std;

const int n = 25;

int main()
{
	char numbers[n]; //jakas tablica liter (tylko te duze dla uproszczenia)
	
	for (int i = 0; i < n; i++) //nadawanie im wartosci z tablicy asci
		numbers[i] = i + 65;

	for (int i = 0; i < n; i++) //wypisujemy po cztery litery (dla wiekszej ilosci to by byla zmora)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				for (int e = 0; e < n; e++) {
					cout << numbers[i] << " " << numbers[j] << " " << numbers[k] << " " << numbers[e] << endl; //wypisywanie danej kombinacji

					if (numbers[i] == 'J' &&numbers[j] == 'U' &&numbers[k] == 'D' &&numbers[e] == 'A') { //dla eksperymentu zatrzymaj sie kidy znajdziez taki wyraz 
						_getch();
					}
				}
	return 0;
}

Problem jest głównie w zagnieżdżonych w sobie pętlach (tyle ile ich jest tyle jest liter w wyrazie) . Oczywiście teraz wyraz jest tylko 4 literowy ale np dla "losowania" całych zdań (tak też zamierzam zrobić) bedzie trzeba użyć przykładowo 20 pętli ,to trochę mało fajne i czytelne :/ . Czy można to jakoś ominąć ,albo może inaczej: Czytelnie ułóżyć ten kod, użyć innego algorytmu ,jak tak to jakiego? . Z góry dziękuje za pomoc i pozdrawiam :)

1
komentarz 13 września przez Knayder Nałogowiec (28,170 p.)
Nie wiem jak ty sobie wyobrażasz losowanie cały zdań!?
Jest 26 liter w alfabecie, a więc przy 20 znakowym zdaniu, takie losowanie to
26^20 przejść pętli.
1.9928149e+28
19928149000000000000000000000.
Tyle raz musi przejść pętla.

Tak na oko policzyłem: Jest to około
3.475546e+17 lat.
347554600000000000 lat

To jest 26329894 razy więcej niż istnieje wszechświat :)

Powodzenia :D
komentarz 13 września przez Jakub 0 Mądrala (5,600 p.)
edycja 13 września przez Jakub 0
No... przesadziłem ,ale tam 7 literowe frekwencje powinny przejść ,to mi liczyło ok 3 min (dokładnie nie wiem bo nie liczyłem ) . Cóż teraz pomyślałem ze to rośnie dość szybko bo o ile moja matma się nie myli to wychodzi n^2 . Ale na kwantowym kompie by przeszło :)

* po za tym nie zależy mi tak bardzo by działanie programu zostało ukończone przed moją śmiercią ... :D ,po prostu będę miał radość że to działa (i że kod jako tako wygląda)
1
komentarz 13 września przez Hipcio Nałogowiec (46,180 p.)

Jakub takie zagnieźdzone pętle idzie uprościć do dwóch pętli (albo nawet jednej) - patrz link. Ewentualnie mógłbyś to też zrobić za pomocą rekurencji.

komentarz 13 września przez Jakub 0 Mądrala (5,600 p.)
dzięki ,z rekurencją mogą być kłopoty ale spróbuje ...

3 odpowiedzi

+5 głosów
odpowiedź 13 września przez mokrowski Nałogowiec (39,180 p.)

Oczywiście można zawsze być wynalazcą koła... ale... 

#include <iostream>
#include <algorithm>
#include <string>

int main() {
    std::string message = "abrakadabra";
    do {
        std::cout << message << '\n';
    } while(std::next_permutation(message.begin(), message.end()));
}

 

1
komentarz 13 września przez Jakub 0 Mądrala (5,600 p.)
no tak... ale kiedy piszę sam coś takiego to ćwiczę algorytmikę (tak samo jak można stworzyć algorytm obliczający silnie a skorzystać z biblioteki cmath)
2
komentarz 13 września przez mokrowski Nałogowiec (39,180 p.)
edycja 13 września przez mokrowski
Ogólnie... bzdura :-)

Oczywiście każde rozwiązanie ma wady i zalety. Aspekt edukacyjny i produkcyjny/zawodowy. Zerknij jednak jak jest implementowane te std::next_permutation abyś wiedział czy pętle które proponujesz są efektywne czy nie. Podpowiem że nie i literatura zna wiele efektywniejszych algorytmów.

Z tym "ćwiczeniem algorytmów" to nie przesadzaj. Jeśli to ma być wymówka do "zrobię jak umiem a nie zerknę na opracowane efektywne rozwiązania", to nauka będzie... nieefektywna i będzie przypominała aspirującego pisarza który ma pomysł że sam nauczy się pisać dobre książki nie czytając innych bo (o zgrozo) mogą go zainspirować :-)
komentarz 13 września przez Jakub 0 Mądrala (5,600 p.)
zgadzam sie z tobą żeby nie zadowalać sie wyłącznie pierwszym niedopracowanym algorytmem . Właśnie dlatego zadałem to pytanie o treści co mogę tu zmienić i jak to inaczej napisać ...
komentarz 13 września przez Jakub 0 Mądrala (5,600 p.)
Po za tym często  muszę szukać gotowych implementacji i je zrozumieć bo własnych napisać nie umiem bez zobaczenia jakiegoś przykładu
+2 głosów
odpowiedź 13 września przez Ehlert VIP (111,550 p.)

Żeby uniknąć zagnieżdżania i zrobić program który docelowo sprawdzi wszystkie możliwe kombinacje potrzebujesz funkcji, która będzie generować kolejne warianty stringów zawierających odpowiednie znaki.

/**
 * Function returns next string in brute-force queue
 * Returning strings contain only printable chars
 * Examples
 * for " "      return "!"
 * for "~"      return "  "
 * for "~ "     return "~!"
 *
 * @param std::string src
 *
 * @return std::string next string
 */
std::string nextWord(std::string & src)
{
    std::string result = src;
    bool nextChar = true;
    for (auto iter = result.rbegin(); iter != result.rend(); ++iter) {
        if (*iter < 126) {
            (*iter)++;
            nextChar = false;
            break;
        } else {
            (*iter) = 32;
        }
    }
    if (nextChar) {
        result += ' ';
    }
    return result;
}
komentarz 13 września przez Ehlert VIP (111,550 p.)

Bardzo chętnie usłyszę opinię kogoś bardziej ogarniętego z C++ na temat tego rozwiązania cheeky

komentarz 14 września przez Jakub 0 Mądrala (5,600 p.)
Dzięki za pomoc ale tak słabo rozumiem działanie algorytmu . Czy mógł byś wytłumaczyć z grubsza jego  tok działania ? Z góry dziękuje
1
komentarz 14 września przez Ehlert VIP (111,550 p.)

Otwórz sobie tablicę ASCII i przetestuj. Dla ciągu abba zwróci abbb, abbc, abbd i tak dalej aż do ~~~~. Potem zacznie sprawdzanie od pięciu spacji "     ", "    !"  itd. 

+1 głos
odpowiedź 14 września przez mokrowski Nałogowiec (39,180 p.)
A ja proponował bym rozważyć inną drogę "nie kombinatoryczną". Jeśli wyrazy mają być sensowne (i w konsekwencji możliwe do poprawnego wymówienia), to obowiązują inne zasady niż brutalne generowanie zestawień liter. Raczej kombinacje spółgłosek, samogłosek, ich rodzajów. Np. wyraz "żaba" to "spółgłoska, samogłoska, spółgłoska, samogłoska" :-) A to tylko jeden ze wzorców ale "sensowniejszy językowo" niż "ffff" :-)
komentarz 14 września przez Jakub 0 Mądrala (5,600 p.)
dobra rada :) ,spróbuje napisać coś takiego dla ćwiczeń ... Swoją drogą napisałem ten algorytm by uzyskać taki efekt jak w programach do odgadywania haseł ,chociaż wiem że do tego jeszcze daleko :D

Podobne pytania

0 głosów
2 odpowiedzi 570 wizyt
pytanie zadane 19 grudnia 2016 w C i C++ przez Hipcio Nałogowiec (46,180 p.)
0 głosów
1 odpowiedź 157 wizyt
0 głosów
2 odpowiedzi 100 wizyt
pytanie zadane 10 marca w Inne języki przez hoktaur Pasjonat (18,790 p.)

41,475 zapytań

80,496 odpowiedzi

159,288 komentarzy

19,796 pasjonatów

Przeglądających: 305
Pasjonatów: 18 Gości: 287

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...