Dato una serie di città e distanza tra ogni coppia di città, il problema è trovare il tour più breve possibile che visita ogni città esattamente una volta e ritorna al punto di partenza.
Problema: dati i 2 processi i e j, è necessario scrivere un programma in grado di garantire la mutua esclusione tra i due senza alcun supporto hardware aggiuntivo.
Generazione di array ordinati casuali Memorizziamo gli elementi di un array casuale in un array, quindi lo ordiniamo e lo stampiamo.
Dato un numero 'n' e n numeri, ordinare i numeri utilizzando l'ordinamento simultaneo. (Suggerimento: prova a utilizzare le chiamate di sistema shmget, shmat). Parte 1: l'algoritmo (COME?) Crea ricorsivamente due processi secondari, uno per la metà sinistra, uno per la metà destra. Se il numero di elementi nell'array per un processo è inferiore a 5, eseguire un ordinamento per inserimento. Il genitore dei due figli unisce quindi il risultato e ritorna al genitore e così via. Ma come renderlo simultaneo?Parte 2: La logica (PERCHÉ?) La parte importante della soluzione a questo problema non è algoritmica, ma spiegare i concetti di sistema operativo e kernel. Per ottenere un ordinamento simultaneo, abbiamo bisogno di un modo per far sì che due processi funzionino contemporaneamente sullo stesso array. Per rendere le cose più semplici Linux fornisce molte chiamate di sistema tramite semplici endpoint API. Due di essi sono shmget() (per l'allocazione della memoria condivisa) e shmat() (per le operazioni sulla memoria condivisa). Creiamo uno spazio di memoria condiviso tra il processo figlio che forziamo. Ogni segmento è diviso in figlio sinistro e figlio destro che vengono ordinati, la parte interessante è che lavorano contemporaneamente! shmget() richiede al kernel di allocare una pagina condivisa per entrambi i processi. Perché il tradizionale fork() non funziona? La risposta sta in ciò che fa effettivamente fork(). Dalla documentazione, "fork() crea un nuovo processo duplicando il processo chiamante". Il processo figlio e il processo genitore vengono eseguiti in spazi di memoria separati. Al momento di fork() entrambi gli spazi di memoria hanno lo stesso contenuto. Le scritture in memoria, le modifiche al descrittore di file (fd), ecc., eseguite da uno dei processi non influiscono sull'altro. Quindi abbiamo bisogno di un segmento di memoria condivisa.
Dato un array di numeri interi positivi, sostituire ciascun elemento dell'array in modo tale che la differenza tra gli elementi adiacenti nell'array sia inferiore o uguale a un dato obiettivo. Dobbiamo minimizzare il costo di aggiustamento, cioè la somma delle differenze tra i nuovi e i vecchi valori. Fondamentalmente dobbiamo minimizzare ?|A[i] - Anew[i]| dove 0? io ? n-1, n è la dimensione di A[] e Anew[] è l'array con differenza adiacente inferiore o uguale alla destinazione. Supponiamo che tutti gli elementi dell'array siano inferiori alla costante M = 100.
Dato un numero intero n che rappresenta il numero di cifre. L'attività è stampare tutti i numeri di n cifre in modo tale che la differenza assoluta tra la somma delle cifre nelle posizioni pari e nelle posizioni dispari sia esattamente 1. Nota: il numero non deve iniziare con 0 (non sono consentiti zeri iniziali).
Dato un semplice albero delle espressioni, costituito da operatori binari di base, ovvero +, -,* e / e alcuni numeri interi, valutare l'albero delle espressioni.
Dato il numero di cifre n, stampa tutti i numeri di n cifre la cui somma delle cifre dà la somma data. La soluzione non deve considerare gli 0 iniziali come cifre.Esempi:
Dati due array interi, aggiungi i loro elementi nel terzo array soddisfacendo i seguenti vincoli:
Dato un array di numeri interi, verificare se è possibile rimuovere esattamente un intero dall'array che divide l'array in due sottoarray con la stessa somma.
Dato un array che contiene sia numeri interi positivi che negativi, trovare il prodotto del sottoarray del prodotto massimo. La complessità temporale prevista è O(n) e può essere utilizzato solo O(1) spazio aggiuntivo.
Dato un array arr[] e un intero k, trova l'array dopo aver invertito ogni sottoarray di k elementi consecutivi al suo posto. Se l'ultimo sottoarray ha meno di k elementi, invertirlo così com'è. Modifica l'array sul posto, non restituisce nulla.
Data una lista di numeri interi, riorganizzare la lista in modo che consista nell'alternanza di elementi minimi massimi utilizzando solo operazioni di lista. Il primo elemento dell'elenco dovrebbe essere il minimo e il secondo elemento dovrebbe essere il massimo di tutti gli elementi presenti nell'elenco. Allo stesso modo, il terzo elemento sarà il successivo elemento minimo e il quarto elemento sarà il successivo elemento massimo e così via. Non è consentito l'utilizzo di spazi aggiuntivi. Esempi:
Dato un intervallo [n,m], trova il numero di elementi che hanno un numero dispari di fattori nell'intervallo dato (n e m compresi). Esempi:
Dato un array binario di dimensione n dove n > 3. Un valore vero (o 1) nell'array significa attivo e falso (o 0) significa inattivo. Dato un numero k, il compito è trovare il conteggio delle celle attive e inattive dopo k giorni. Dopo ogni giorno, lo stato della cella i-esima diventa attivo se le celle sinistra e destra non sono le stesse e inattivo se la cella sinistra e destra sono uguali (entrambi 0 o entrambi 1).
Dato un array di n numeri interi univoci in cui ogni elemento dell'array è compreso nell'intervallo [1, n]. L'array ha tutti elementi distinti e la dimensione dell'array è (n-2). Quindi in questo array mancano due numeri dell'intervallo. Trova i due numeri mancanti.
Dato un array ordinato di n valori distribuiti uniformemente arr[], scrivere una funzione per cercare un particolare elemento x nell'array. La ricerca lineare trova l'elemento in tempo O(n), la ricerca per salto richiede tempo O(n) e la ricerca binaria richiede tempo O(log n). La ricerca per interpolazione rappresenta un miglioramento rispetto alla ricerca binaria per le istanze, in cui i valori in un array ordinato sono distribuiti uniformemente. L'interpolazione costruisce nuovi punti dati all'interno dell'intervallo di un insieme discreto di punti dati noti. La ricerca binaria va sempre all'elemento centrale per verificare. D'altra parte, la ricerca per interpolazione può andare in posizioni diverse a seconda del valore della chiave da cercare. Ad esempio, se il valore della chiave è più vicino all'ultimo elemento, è probabile che la ricerca per interpolazione inizi la ricerca verso il lato finale. Per trovare la posizione da cercare, utilizza la seguente formula.
Dato un array di n elementi distinti. Trova il massimo del prodotto del minimo di due numeri nell'array e la differenza assoluta delle loro posizioni, ovvero trova il valore massimo di abs(i - j) * min(arr[i], arr[j]) dove i e j variano da 0 a n-1.
Dato un array contenente numeri positivi e negativi. La matrice rappresenta i checkpoint da un'estremità all'altra della strada. I valori positivi e negativi rappresentano la quantità di energia in quel punto di controllo. I numeri positivi aumentano l’energia mentre i numeri negativi la diminuiscono. Trova l'energia iniziale minima richiesta per attraversare la strada in modo tale che il livello di energia non diventi mai 0 o inferiore a 0.
