Attualmente sto seguendo AP Computer Science nel mio liceo e mentre osservavo alcuni esempi di problemi con i test AP mi sono imbattuto in uno che mi ha davvero confuso.
Problema di esempio
La risposta al problema è la lettera A, ma non sembra capire perché questa sia la risposta o come iniziare a provare a risolvere un problema come questo.
Il codice è una funzione ricorsiva, nel senso che si richiama continuamente, ogni volta riducendo la dimensione del problema fino a raggiungere un punto in cui non si chiama più ma restituisce un valore. Affinché riducano la dimensione del problema con ogni chiamata, ciò che fanno è passare una versione modificata dei parametri che hanno ricevuto nella chiamata precedente.
Questo tipo di domande richiede di "eseguire il programma nella tua testa" , nel senso di cercare di seguire il percorso di esecuzione e di essere in grado, almeno in una certa misura, di tenere a mente i valori delle variabili per riprodurre "nella tua testa" cosa farebbe il computer con il codice. Fondamentalmente ti stanno chiedendo di interpretare ed eseguire il programma nel tuo cervello. Ovviamente puoi usare carta e penna per aiutare te stesso. È ovvio anche il fatto che devi avere alcune conoscenze di programmazione di base.
Naturalmente è più facile una volta che sappiamo che la risposta è A.
Si chiama la funzione passandogli gli indici del primo e dell'ultimo elemento dell'array, nonché il numero che si desidera trovare quanti elementi dell'array sono inferiori a, dato che l'array è ordinato e non ci sono duplicati .
Prima trovano una posizione centrale approssimativa dell'array.
Se l'elemento centrale dell'array è inferiore a num , la funzione chiama se stessa passando solo la metà superiore dell'array (in realtà i valori dell'indice che passano farebbero sì che la funzione elabori solo la metà superiore dell'array).
Se l'elemento centrale dell'array è maggiore di num , la funzione chiama se stessa passando solo la metà inferiore dell'array (in realtà i valori dell'indice che passano farebbero sì che la funzione elabori solo la metà inferiore dell'array).
Questi due passaggi dividono il problema a metà ogni volta.
C'è un momento, dopo il numero X di chiamate, che si verifica una delle seguenti situazioni:
Abbiamo ridotto il problema a tal punto che ora gli indici sono esauriti ( low e high si sovrappongono).
Troviamo un numero uguale a num .
Nel primo caso significherebbe che non ci sono elementi nell'array che sono inferiori a num (perché abbiamo iniziato con uno zero indice inferiore), quindi zero è il numero di elementi inferiore a num .
Nel secondo caso significherebbe che l'indice dell'elemento è quanti elementi nell'array sono inferiori a num .
In entrambi gli ultimi due casi, la funzione non si chiama più e il valore viene restituito alla traccia di chiamata dello stack.
Funziona solo perché gli elementi sono ordinati e non ci sono valori duplicati. Se esistevano valori duplicati e il programma termina a causa della seconda condizione di fine ( arr[mid]==num ) il valore restituito sarebbe errato perché, al di fuori del numero di elementi restituiti, almeno uno non sarebbe inferiore ma uguale a n .
Passa attraverso la funzione utilizzando alcuni dati effettivi.
Le condizioni preliminari indicano che l'array di input verrà preselezionato, senza duplicati. Facciamo un tale array (questo sarà per lo più pseudocodice):
arr = { 1,2,3,5,7,8,12,16,17,18 } // an array with 10 sorted, non-repeating values.
Se scegliamo 6 per num , la chiamata
mystery(0, arr.Length-1, num);
ora diventa:
mystery(0, 9, 6);
Lo lascerò a te come esercizio per camminare attraverso la funzione usando quei valori.
Non dimenticare che, in linguaggi di tipo C, l'indice dell'array inizia a zero, quindi gli indici degli elementi dell'array di cui sopra contano da zero a 9.
Leggi altre domande sui tag array computer-science problem-solving