Tenint en compte un conjunt de ciutats i distància entre cada parell de ciutats, el problema és trobar el recorregut més curt possible que visiti cada ciutat exactament una vegada i torni al punt de partida.
Problema: Tenint en compte el procés I i J, heu d’escriure un programa que pugui garantir l’exclusió mútua entre tots dos sense cap suport de maquinari addicional.
Generant matrius ordenades aleatòries, emmagatzemem els elements de matriu aleatoris en una matriu i després l’ordenem i la imprimeix.
Donats un nombre "n" i un nombre n, ordena els números mitjançant l'Ordenació de combinació simultània. (Suggeriment: proveu d'utilitzar trucades al sistema shmget, shmat).Part 1: l'algorisme (COM?) Feu de manera recursiva dos processos secundaris, un per a la meitat esquerra i un per a la meitat dreta. Si el nombre d'elements de la matriu d'un procés és inferior a 5, feu una ordenació per inserció. Aleshores, el pare dels dos fills fusiona el resultat i torna al pare i així successivament. Però, com ho feu simultània?Part 2: la lògica (PER QUÈ?) La part important de la solució d'aquest problema no és algorítmica, sinó explicar conceptes de sistema operatiu i nucli. Per aconseguir una ordenació simultània, necessitem una manera de fer que dos processos funcionin a la mateixa matriu alhora. Per facilitar les coses, Linux ofereix moltes trucades al sistema mitjançant punts finals d'API simples. Dos d'ells són, shmget() (per a l'assignació de memòria compartida) i shmat() (per a operacions de memòria compartida). Creem un espai de memòria compartida entre el procés fill que bifurquem. Cada segment es divideix en fill esquerre i dret que s'ordena, la part interessant és que estan treballant simultàniament! El shmget() demana al nucli que assigni una pàgina compartida per als dos processos. Per què el tradicional fork() no funciona? La resposta rau en què fa realment fork(). A la documentació, "fork() crea un procés nou duplicant el procés de trucada". El procés fill i el procés pare s'executen en espais de memòria separats. En el moment de fork() ambdós espais de memòria tenen el mateix contingut. Les escriptures de memòria, els canvis de descriptors de fitxers (fd), etc. realitzats per un dels processos no afecten l'altre. Per tant, necessitem un segment de memòria compartida.
Donada una matriu d'enters positius, substituïu cada element de la matriu de manera que la diferència entre els elements adjacents de la matriu sigui menor o igual a un objectiu donat. Hem de minimitzar el cost d'ajust, és a dir, la suma de les diferències entre els valors nous i antics. Bàsicament hem de minimitzar ?|A[i] - Anew[i]| on 0? jo? n-1, n és la mida de A[] i Anew[] és la matriu amb diferència adjacent inferior o igual a l'objectiu. Suposem que tots els elements de la matriu són menors que la constant M = 100.
Requisits previs: BIT, DFS
Donat un nombre enter n que representa el nombre de dígits. La tasca és imprimir tots els nombres de n dígits de manera que la diferència absoluta entre la suma de dígits a les posicions parelles i les posicions senars sigui exactament 1. Nota: el nombre no ha de començar per 0 (no es permeten zeros inicials).
Donat un arbre d'expressions simple, format per operadors binaris bàsics, és a dir, + , - ,* i / i alguns nombres enters, avalueu l'arbre d'expressions.
Donat el nombre de dígits n, imprimiu tots els nombres d'n dígits la suma de dígits dels quals suma la suma donada. La solució no hauria de considerar els 0 inicials com a dígits. Exemples:
Donades dues matrius senceres, afegiu els seus elements a la tercera matriu satisfent les restriccions següents:
Donada una matriu que conté nombres enters positius i negatius, trobeu el producte del subarray màxim del producte. La complexitat del temps esperat és O(n) i només es pot utilitzar l'espai addicional O(1).
Donada una matriu arr[] i un nombre enter k, trobeu la matriu després d'invertir cada subarray de k elements consecutius al seu lloc. Si l'últim subbarrat té menys de k elements, inverteix-lo tal com està. Modifiqueu la matriu al seu lloc, no retorneu res.
Donada una llista de nombres enters, reorganitzeu la llista de manera que consisteixi en alternar elements mínims màxims utilitzant només operacions de llista. El primer element de la llista ha de ser el mínim i el segon element ha de ser el màxim de tots els elements presents a la llista. De la mateixa manera, el tercer element serà el següent element mínim i el quart element serà el següent element màxim i així successivament. No es permet l'ús d'espai addicional. Exemples:
Donat un interval [n,m], trobeu el nombre d'elements que tenen un nombre senar de factors en l'interval donat (n i m inclosos). Exemples:
Donada una matriu binària de mida n on n > 3. Un valor vertader (o 1) a la matriu significa actiu i fals (o 0) significa inactiu. Donat un nombre k, la tasca és trobar el recompte de cel·les actives i inactives després de k dies. Després de cada dia, l'estat de la cel·la i s'activa si les cel·les esquerra i dreta no són iguals i inactiva si la cel·la esquerra i dreta són iguals (ambdues 0 o 1).
Donada una matriu de n nombres enters únics on cada element de la matriu es troba en el rang [1, n]. La matriu té tots els elements diferents i la mida de la matriu és (n-2). Per tant, falten dos nombres de l'interval d'aquesta matriu. Troba els dos nombres que falten.
Donada una matriu ordenada de n valors distribuïts uniformement arr[], escriviu una funció per cercar un element x concret a la matriu. La cerca lineal troba l'element en temps O(n), Jump Search triga O(n) temps i Binary Search pren temps O(log n). La cerca d'interpolació és una millora respecte a la cerca binària per als casos en què els valors d'una matriu ordenada es distribueixen uniformement. La interpolació construeix nous punts de dades dins del rang d'un conjunt discret de punts de dades coneguts. La cerca binària sempre va a l'element central per comprovar-ho. D'altra banda, la cerca per interpolació pot anar a diferents ubicacions segons el valor de la clau que s'està cercant. Per exemple, si el valor de la clau està més a prop de l'últim element, és probable que la cerca per interpolació comenci la cerca cap al costat final. Per trobar la posició a cercar, utilitza la fórmula següent.
Donada una matriu de n elements diferents. Trobeu el màxim del producte de Mínim de dos nombres a la matriu i la diferència absoluta de les seves posicions, és a dir, trobeu el valor màxim de abs(i - j) * min(arr[i], arr[j]) on i i j varien de 0 a n-1.
Donada una matriu que conté nombres positius i negatius. La matriu representa els punts de control d'un extrem a l'altre extrem del carrer. Els valors positius i negatius representen la quantitat d'energia en aquest punt de control. Els nombres positius augmenten l'energia i els negatius disminueixen. Trobeu l'energia inicial mínima necessària per creuar el carrer de manera que el nivell d'energia mai sigui 0 o inferior a 0.
Donada una matriu de cadenes, la tasca és imprimir la cadena amb el nombre màxim de caràcters únics.
