Un modo di verificare se le cifre del num1 sono le cifre in num2 senza controllare ogni cifra?

StackOverflow https://stackoverflow.com/questions/567165

  •  05-09-2019
  •  | 
  •  

Domanda

Diciamo che ho immaginato un numero della lotteria di:

  

1689

E il modo in cui la lotteria funziona è, l'ordine delle cifre non importa fino a quando le cifre corrispondono 1:. 1 con le cifre del numero effettivo vincente della lotteria

Quindi, il numero 1689 sarebbe un numero vincente della lotteria con:

  

1896, 1698, 9816, ecc ..

Fino a quando ogni cifra nella tua ipotesi era presente nel numero di destinazione, allora si vince la lotteria.

C'è un modo matematico posso fare questo?

Ho risolto questo problema con un O (N ^ 2) annodare verifica ogni cifra contro ogni cifra del numero vincente della lotteria (separandoli con modulo). Il che va bene, funziona, ma vorrei sapere se ci sono trucchi di matematica pulito che posso fare.

Per esempio, in un primo momento ... ho pensato che avrei potuto essere difficile e basta prendere la somma e prodotto di ciascuna cifra in entrambi i numeri e se abbinati poi vinto.

^ Pensi che avrebbe funzionato?

Tuttavia, ho smentito rapidamente questo quando ho scoperto che lotteria indovinare: 222, e 124 hanno le cifre diverse ma lo stesso prodotto e somma

.

Qualcuno sa qualsiasi trucchi di matematica che posso usare per determinare rapidamente se le cifre in num1 corrispondono alle cifre in num2 indipendentemente dall'ordine?

È stato utile?

Soluzione

Che ne dite di passare attraverso ogni numero, e contando il numero di presenze di ogni cifra (in due diverse matrici 10 elementi)? Dopo che aveva fatto il totale, confrontare i conti di ogni cifra. Dal momento che si guarda solo al ciascuna cifra una volta, questo è O (N).

Codice sarebbe simile: 

for(int i=0; i<digit_count; i++)
{
   guessCounts[guessDigits[i] - '0']++;
   actualCounts[actualDigits[i] - '0']++;
}

bool winner = true;
for(int i=0; i<10 && winner; i++)
{
   winner &= guessCounts[i] == actualCounts[i];
}

Sopra il codice fa l'ipotesi che guessDigits e actualDigits sono entrambe le stringhe char; se hanno tenuto le cifre effettive allora si può saltare il business - '0'.

Probabilmente ci sono ottimizzazioni che renderebbero questo prende meno spazio o terminare prima, ma è un esempio abbastanza semplice di un approccio O (N).

A proposito, come ho già detto in un commento, il confronto moltiplicazione / somma sarà sicuramente non funzionare a causa di zeri. Considerare 0123 e 0222. Il prodotto è 0, somma è 6 in entrambi i casi.

Altri suggerimenti

Suddiviso in array, ordinare array, unire nella stringa, confrontare le stringhe.

(Non è un trucco per la matematica, lo so)

È possibile inserire le cifre in un array, ordinare l'array, quindi confrontare l'elemento array per elemento. Questo vi darà O (N log N) complessità che è meglio di O (N ^ 2).

Se N può diventare grandi, l'ordinamento le cifre è la risposta.

A causa cifre sono 0..9 è possibile contare il numero di occorrenze di ogni cifra della risposta lotteria in un array [0..9].

Per confrontare si può sottrarre 1 per ogni cifra si incontrano nel indovinare. Quando si incontra una cifra dove il conteggio è già 0, si conosce la congettura è diverso. Quando si arriva attraverso tutte le cifre, l'ipotesi è lo stesso (a condizione che l'ipotesi ha il maggior numero di cifre come la risposta della lotteria).

Per ogni cifra d moltiplicano con la (d + 1) -esimo numero primo.

Questo è più matematica, ma meno efficiente rispetto ai metodi di ordinamento o secchio. In realtà è il metodo secchio sotto mentite spoglie.

Mi piacerebbe a ordinare le cifre del numero e confrontarli.

Se sei solo a che fare con 4 cifre non penso che devi mettere molto pensiero in quale algoritmo si utilizza. Saranno tutti di eseguire o meno la stessa.

Anche 222 e 124 non hanno la stessa somma

Dovete considerare che, quando n è piccolo, l'ordine di efficienza è irrilevante, e le costanti di iniziare a importare di più. Quanto grande può vostri numeri effettivamente ottenere? Si può arrivare fino a 10 cifre? 20? 100? Se i numeri hanno poche cifre, n ^ 2 non è poi così male. Se si dispone di stringhe di migliaia di cifre, allora si potrebbe effettivamente bisogno di fare qualcosa di più intelligente come l'ordinamento o bucket. (Vale a dire contare gli 0, contare le 1s, ecc.)

sto rubando la risposta da Yuliy, e starblue (li upvote)

bucket è il più veloce a parte la O (1) 

lottonumbers == mynumbers;

L'ordinamento è O (nlog2n)

bucket sort è un algoritmo O (n).

Quindi, tutto quello che dovete fare è farlo due volte (una volta per i numeri, una volta per il target-set), e se i numeri delle cifre si sommano, poi si corrispondono. Qualsiasi tipo di ordinamento è un overhead aggiunto che non è necessaria in questo caso. 

array[10] digits;
while(targetnum > 0)
{
    short currDig = targetnum % 10;
    digits[currDig]++;
    targetnum = targetnum / 10;
}
while(mynum > 0)
{
    short myDig = mynum % 10;
    digits[myDig]--;
    mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
   if(digits[i] == 0)
      continue;
   else
     //FAIL TO MATCH
}

Non il codice più bello, lo ammetto.

Crea un array di 10 interi subscripted [0 .. 9].

inizializzare ogni elemento per un numero primo diverso

Set prodotto 1.

Utilizzare ogni cifra del numero, a pedice nella matrice, estrarre il numero primo, e moltiplicare il prodotto da esso.

Che ti dà una rappresentazione unica, che è ordine cifre indipendente.

Fare la stessa procedura per l'altro numero.

Se le rappresentazioni uniche corrispondono, allora i numeri partita originale.

Se non ci sono cifre ripetute consentiti (non so se questo è il caso però) quindi utilizzare un numero binario a 10 bit. Il bit più significativo rappresenta la cifra 9 e la LSB rappresenta il lavoro cifra 0. attraverso ogni numero, a sua volta e capovolgere il bit appropriato per ogni cifra che si trova

1689 sarebbe: 1.101.000,01 mila

e 9816 sarebbe anche: 1.101.000,01 mila

poi un XOR o un sottrarre lasceranno 0 se si è un vincitore

Questa è solo una semplice forma di bucket

Solo per divertimento, e pensare al di fuori del normale, invece di smistamento e altri modi, fanno la cancellazione-cosa. Se ResultString è vuoto, si ha un vincitore! 

    Dim ticket As String = "1324"
    Dim WinningNumber As String = "4321"

    For Each s As String In WinningNumber.ToCharArray
        ticket = Replace(ticket, s, "", 1, 1)
    Next

    If ticket = "" Then MsgBox("WINNER!")
    If ticket.Length=1 then msgbox "Close but no cigar!"

Questo funziona con la ripetizione numeri troppo ..

Ordina cifre prima memorizzazione di un numero. Dopo di che, i numeri saranno uguali.

Una soluzione sveglio è quello di utilizzare una variante di Zobrist hashing . (Sì, lo so che è eccessivo, così come probabilistica, ma hey, è "intelligente".)

inizializzare una decina di elemento della matrice a[0..9] di interi casuali. Poi, per ogni numero d[], calcolare la somma dei a[d[i]]. Se i numeri contenevano le stesse cifre, i numeri risultanti saranno uguali; con alta probabilità (~ 1 in quanti possibili interi ci sono), è vero il contrario pure.

(Se si sa che ci saranno al massimo 10 cifre totale, quindi è possibile utilizzare i numeri fissi 1, 10, 100, ... invece di numeri casuali per il successo garantito. Questo è l'ordinamento secchio in non-troppo- molto travestimento.)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top