PureBasic

Forums PureBasic
Nous sommes le Jeu 21/Nov/2019 20:44

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page Précédente  1 ... 3, 4, 5, 6, 7  Suivante
Auteur Message
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Ven 06/Avr/2018 23:22 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
Fig a écrit:
Par contre si pour chaque élement tu passe en revu tout les autres élement ça reste une réponse en O(n²)


oui, mais c'est LA seule solution, pour ne rien louper !
si tu ne passe pas en revu tout les elements, tu prends le risque de louper des pairs possibles ....

la solution pour ne rien louper c'est celle-ci entre autre :
(avec l'emloi de 2 pointeurs de données de 2 boucles ) tu es sur de ressortir toutes les paire possibles

si tu n'emploi pas ce systeme , tu risque de louper des paires possible , car tout tes elements ne seront pas pris en compte

mais a ce stade,j'ai peut etre pas compris le but final .... :)

Code:
;***********************************************
;Titre  :*bidouille
;Auteur  : Zorro
;Date  :06/04/2018
;Heure  :09:51:20
;Version Purebasic :  PureBasic 5.62 (Windows - x86)
;Version de l'editeur :EPB V2.68
; Libairies necessaire : Aucune
;***********************************************

Declare rotation()
;soit un tableau rempli de nombres positifs non triés,
; ;
Global Dim tab(100)

For i=1 To ArraySize(tab())
            Tab(i)=Random(50,1)         
Next i





;
; ;
;  Global Dim tab(4)



;  tab(1)=5
;  tab(2)=7
;  tab(3)=2
;  tab(4)=6


;



Global Somme_a_trouver=8

;trouver la paire qui correspond à une somme donnée en O(n)...
; on recherche

For y=1 to ArraySize(tab())
      For x=1 To ArraySize(tab())
            if x<>y
                  a=Tab(y)
                  C=Tab(x)
                  If a+C=Somme_a_trouver
                        Debug " la paire : "+"["+Str(A)+";"+Str(c)+"]"+" forme la somme a trouver ="+Str(Somme_a_trouver)
                        Break
                  Endif
            Endif
      Next x
      
Next y

debug "fin"

; Epb

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 9:43 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@Fig
Après m'avoir bien trituré les méninges, comme zorro je suis persuadé qu'il faut d'une manière ou d'une autre deux boucles pour obtenir le résultat. (Ou je n'est rien compris)
Il faut bien prendre chaque indice du tableau, et le comparé avec les autres pour trouver une paire valable. :?:
J'ai hâte de voir ta solution 8O :lol:
@ Zorro
La comparaison peut être a+c ou a-c :wink:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 10:36 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Voila ma solution... Je suis sûr que ça va vous paraître évident maintenant.
Pour plus de souplesse et pour économiser de la mémoire, on peut utiliser une map (table de hachage). (ça ne changera rien au O(n))
Mais dans le principe, ça donne ça:

Code:
;Somme à trouver
#somme=8
;tableau des #nbElement valeurs
#nbElement=5
;valeur maximale des élements
#valeur_max=12
Dim Tableau.i(#nbElement) ;remplissage du tableau
For i=1 To #nbElement
    tableau(i)=Random(#valeur_max,1)
    ;Debug Tableau(i)
Next i

;tableau des compléments ou map si on le souhaite...
Dim comp.i(#valeur_max)

;on passe en revu chaque élément. Pour chacun d'eux, on vérifie si on a déja croisé par le passé son complément, sinon on le rajoute
For i=1 To #nbElement ;On a O(1) x N soit O(N) pour le traitement de tous les élements
    element.i=tableau(i) ;temps constant O(1)
    complement.i=#somme-element:If complement<0:Continue:EndIf
   
    ;vérifie si le complément de la valeur actuelle a déja été vue.
    If comp(complement) ;temps constant O(1)
        ;dans ce cas on a une paire
        MessageRequester("Résultat","La paire est "+Str(tableau(i))+";"+Str(tableau(comp(complement))))
        End
    Else ;sinon on le rajoute
        comp(element)=i ;temps constant O(1)
    EndIf
Next i
MessageRequester("Résultat","Pas de paire trouvée")
End

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 12:36 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
:roll: :roll: :roll:

on a tellement l'habitude de penser Tableau dans une boucle et scan de celui-ci depuis le debut
qu'on en oublie qu'una case d'un tableau peut etre accedé en mode direct par son index !! :oops: :oops:
Code:
If comp(complement)


bien vu ... purée , je vais arreter la prog , et faire autre chose moi ... :lol:

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 13:16 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@Fig

Ou j'ai rien compris ou il y a un problème de fonctionnement :?:
Code:
;Somme à trouver
#somme= 10
;tableau des #nbElement valeurs
#nbElement=10
;valeur maximale des élements
#valeur_max=100
Dim Tableau.i(#nbElement) ;remplissage du tableau
; For i=1 To #nbElement
;     tableau(i)=Random(#valeur_max,1)
;     Debug Tableau(i)
; Next i
tableau(1)=24:tableau(2)=81:tableau(3)= 73:tableau(4)= 41:tableau(5)=51:tableau(6)= 67:tableau(7)= 2:tableau(8)= 99:tableau(9)= 57:tableau(10)=26
;tableau des compléments ou map si on le souhaite...
Dim comp.i(#valeur_max)
;on passe en revu chaque élément. Pour chacun d'eux, on vérifie si on a déja croisé par le passé son complément, sinon on le rajoute
For i=1 To #nbElement
    element.i=tableau(i)
    complement.i=#somme-element:If complement<0:Continue:EndIf
   
    ;vérifie si le complément de la valeur actuelle a déja été vue.
    If comp(complement)
        ;dans ce cas on a une paire
        MessageRequester("Résultat","La paire est "+Str(tableau(i))+";"+Str(tableau(comp(complement))))
        End
    Else ;sinon on le rajoute
        comp(element)=i
    EndIf
  Next i

MessageRequester("Résultat","Pas de paire trouvée")

End



51-41 font bien 10 il me semble :wink:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 13:31 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
On cherche la somme pas la différence... La paire 41;51 fait 92...
Je me sers du complément car si tu as un 4 et que tu cherche à faire une somme de 10, il faut que tu trouve un 6... (10-4)

Question 4: (plus simple)
Trouvez si deux rectangles (définis par leurs points haut-gauche et bas-droit) se chevauchent (subsidiaire, savoir si ils se confondent, ou se touchent).

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Dernière édition par Fig le Sam 07/Avr/2018 14:09, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 14:07 
Hors ligne

Inscription: Jeu 05/Fév/2009 17:58
Messages: 923
@ Fig
Ok j'ai pas compris :oops: J'ai pensé une somme, mais pas la somme de deux paires.
Déformation professionnel: Comme je travail beaucoup pour des financiers ou des cabinets d'avocats. J'ai très souvent a rechercher dans des tableaux de chiffres des écarts ou des similitudes
mais rarement la somme de deux chiffres dans un même tableau.
D'ailleurs je vais avoir dans les semaines qui viennent beaucoup de travail.de fait je n'aurais pas le temps pour ton problème de triangles.
Merci pour ces exercices
Michel


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 14:55 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
pour les collisions j'avais fait ça a une epoque

une procedure de "Super collision"
elle a la particularité d'indiquer exactement ou a lieu la collision sur un polygone de 4 cotés

je pense que ça repond a la question ....
garder en tete, qu'il s'agit d'une procedure de collision , donc le test n'a lieu qu'au moment de la colision

ça indique si on est dessous, dessus, a gauche , a droite et aussi en bas a gauche, en bas a droite , en haut a gauche, en haut a droite
et Dedans ou en dehors ....
bougez la souris pour voir ce qui est ecrit en haut a gauche de l'ecran :)


Code:

; prg realisé par Dobro
#dobro=1
#Police=1
#sprite=1

Declare.s super_collision(sprite_numero1, x_sprite1, y_sprite1, sprite_numero2, x_sprite2, y_sprite2)
; cette procedure renvoie du quelle coté le sprite a été touché !

; sprite_numero1= le numero du sprite 1 a tester
;  largeur_spr1 = largeur en pixel du sprite numero 1
; hauteur_spr1 = hauteur en pixel du sprite numero 1
; x_sprite1 = coordonée X du sprite numero 1
; y_sprite1=coordonée Y du sprite numero 1
; --------------------------------------------------------------------------
; sprite_numero2=  le numero du sprite 2 a tester
;  largeur_spr2 = largeur en pixel du sprite numero 2
; hauteur_spr12 = hauteur en pixel du sprite numero 2
; x_sprite2 = coordonée X du sprite numero 2
; y_sprite2 coordonée Y du sprite numero 2

Enumeration
      #Window
      #sprite_cible
      #sprite_souris
      #sprite_text
EndEnumeration

Structure sprite
      x.w
      y.w
EndStructure
Dim sprite.sprite(1)

Dim ecran(640,400)
For x = 0 To 640 ; un écran de couleurs aléatoires
      For y = 0 To 400
            r=Random(255)
            G=Random(255)
            b=Random(255)
            c=RGB(r,G,b)
            ecran(x,y)= c
      Next y
Next x
; ***********************************
Resultat = InitSprite()
FontID = LoadFont(#Police, "arial", 18, #PB_Font_Bold )
EcranX = GetSystemMetrics_(#SM_CXSCREEN):;=largeur de l'ecran
EcranY = GetSystemMetrics_(#SM_CYSCREEN):;=hauteur de l'ecran
WindowID = OpenWindow(#Window, 0, 0, 800, 600,  "hello",#PB_Window_SystemMenu|#PB_Window_BorderLess |#PB_Window_ScreenCentered )

Result = OpenWindowedScreen(WindowID(#Window),0,0, 800, 600, 1, 0,0)


CreateSprite( #sprite_cible, 64, 64)  ; sprite exemple
StartDrawing(SpriteOutput( #sprite_cible) ) ; on dessine dedans
      Box(0, 0, 64, 64, RGB($FF,$0,$80))
StopDrawing()

CreateSprite( #sprite_souris, 32, 32)  ; sprite souris
StartDrawing(SpriteOutput( #sprite_souris) ) ; on dessine dedans
      Box(0, 0, 64, 64,RGB($13,$F8,$7))
StopDrawing()

bord$="aucun bord"
CreateSprite(#sprite_text, 150,14)  ; le text
StartDrawing(SpriteOutput(#sprite_text) ) ; on dessine dedans
      DrawText(1,1,bord$,RGB(0,0,0), RGB(255,255,255))
StopDrawing()

Resultat = InitMouse() 
Repeat
      ExamineMouse()
      Event=WindowEvent()
      
      DisplaySprite(#sprite_cible, WindowWidth(#Window) /2+50,  WindowHeight(#Window)/2+100)
      sprite(1)\x=WindowWidth(#Window)/2+50
      sprite(1)\y=WindowHeight(#Window)/2+100
      
      DisplaySprite(#sprite_souris,  MouseX(),   MouseY())
      DisplaySprite( #sprite_text,  10,  10)
      
      bord$=super_collision(#sprite_cible, sprite(1)\x,sprite(1)\y, #sprite_souris,MouseX(), MouseY()) 
      
      
      StartDrawing(SpriteOutput(#sprite_text) ) ; on dessine dedans
            DrawText(1,1,"                              ", RGB(0,0,0), RGB(255,255,255))
            DrawText(1,1,bord$,RGB(0,0,0), RGB(255,255,255))
      StopDrawing()
      If MouseButton(2)
            End
      EndIf
      
      FlipBuffers():; affiche l'ecran
      ClearScreen(RGB(0, 0, 0)) :;efface l'ecran
Until Event=#PB_Event_CloseWindow






Procedure.s super_collision(sprite_numero1, x_sprite1, y_sprite1, sprite_numero2, x_sprite2, y_sprite2)
      ; code Dobro
      spr1_milieu_x=x_sprite1+SpriteWidth(sprite_numero1) /2
      spr1_milieu_y=y_sprite1+SpriteHeight(sprite_numero1)/2
      spr2_milieu_x=x_sprite2+SpriteWidth(sprite_numero2)/2
      spr2_milieu_y=y_sprite2+SpriteHeight(sprite_numero2)/2
      
      spr1_hauteur=SpriteHeight(sprite_numero1)
      spr1_largeur=SpriteWidth(sprite_numero1)
      spr2_hauteur=SpriteHeight(sprite_numero2)
      spr2_largeur=SpriteWidth(sprite_numero2)
      
      
      If SpriteCollision(sprite_numero1,x_sprite1, y_sprite1,sprite_numero2,x_sprite2, y_sprite2)
            If  spr2_milieu_x<x_sprite1 And spr2_milieu_y<y_sprite1
                  bord$="haut-gauche  a cheval               "
                  Goto suite
            EndIf
            
            If  spr2_milieu_x>(x_sprite1+spr1_largeur) And spr2_milieu_y<y_sprite1
                  bord$="haut-droit  a cheval         "
                  Goto suite
            EndIf
            
            If spr2_milieu_x>x_sprite1+spr1_largeur And spr2_milieu_y>y_sprite1+spr1_hauteur
                  bord$="bas-droit  a cheval       "
                  Goto suite
            EndIf
            
            If spr2_milieu_x<x_sprite1 And spr2_milieu_y>y_sprite1+spr1_hauteur
                  bord$="bas-gauche  a cheval"
                  Goto suite
            EndIf
            
            
            
            
            If x_sprite2+spr2_largeur>x_sprite1 And  x_sprite2<x_sprite1+spr1_largeur And spr2_milieu_y<y_sprite1
                  bord$="haut  a cheval       "
                  Goto suite
            EndIf
            
            If  y_sprite2+spr2_hauteur>y_sprite1 And y_sprite2<y_sprite1+spr1_hauteur And spr2_milieu_x>x_sprite1+spr1_largeur
                  bord$="droit  a cheval             "
                  Goto suite
            EndIf
            
            If  x_sprite2+spr2_largeur>x_sprite1 And x_sprite2<x_sprite1+spr1_largeur And spr2_milieu_y>y_sprite1+spr1_hauteur
                  bord$="bas  a cheval            "
                  Goto suite
            EndIf
            
            If  y_sprite2+spr2_hauteur>y_sprite1 And y_sprite2<y_sprite1+spr1_hauteur And  spr2_milieu_x<x_sprite1
                  bord$="gauche  a cheval          "
                  Goto suite
            EndIf
            
            If x_sprite2 > x_sprite1 And (x_sprite2+spr2_largeur) <x_sprite1+spr1_largeur
                  If  y_sprite2>y_sprite1  and  y_sprite2+spr2_hauteur<y_sprite1+spr1_hauteur
                        bord$="Dedans                   "
                        Goto suite
                  Endif
            EndIf
            Else
            
      bord$=" en dehors"
   
            
            
      EndIf
      
      suite:
      ProcedureReturn  bord$
EndProcedure





_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 17:26 
Hors ligne

Inscription: Mar 09/Déc/2014 20:02
Messages: 74
Salut,
pour la soluce "officielle" du prob 3 : c pas clair.

avec ces valeurs :
Code:
tableau(1)=5:tableau(2)=6:tableau(3)=4:tableau(4)=2:Tableau(5)=10:tableau(6)=4:tableau(7)=3


on a comme résultat : paire 2:6
Il suffisait donc de trouver une seule paire dans le tableau ????
Il y a aussi 5;3 et 4;4 avec les données de l'exemple ci dessus.
Comme il n'y a qu'une boucle les autres paires ne sont pas trouvées.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 18:43 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
retire le End de la ligne 27
et repond au dialogue :)

avec le End , ça s'arrete au premier trouvé effectivement

le secret du truc , c'est qu'il utilise un acces direct au tableau
au lieu de l'habituel acces sequentiel des elements d'un tableau

on a l'habitude de scanner l'ensemble des elements d'un tableau pour connaitre la valeur de chaque case

là l'astuce consiste a utiliser un tableau comme si c’était des appartements d'un HLM
il ne met dans une case QUE l'element correspondant au numero de la case (adresse de l'appart ) :lol:

mince ... on est dans la citée .... vite REDIM :mrgreen:

en tout cas c'est bien vu cette utilisation d'un tableau
pourtant je le sais qu'un tableau c'est un ensemble de case memoire
mais je ne sais pas pourquoi , je l'utilise toujours dans une boucle... c'est con hein ? :mrgreen: :lol:

encore que maintenant, je prefere les listes chainées , mon probleme viens surement de ça :)

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 19:47 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
Puisque Dobro avait déja anticipé la question 4... :wink:
Question 5:

On a un tableau dont chaque valeur est la hauteur de la tour.
On part de la tour numéro 0 (indice 0 du tableau) et on souhaite sauter en position 6 en dehors du tableau dans le cas particulier de mon exemple.
On peut sauter de gauche à droite au maximum de la hauteur de la tour sur laquelle on se trouve.
(si on est sur la tour de hauteur 4, on peut sauter 4, 3, 2 ou 1 tour vers la droite)
On ne peut pas sauter une tour plus haute que celle sur laquelle on est.
Si on est sur une tour de hauteur 0, on ne peut plus avancer, on est bloqué, il n'y a pas de solution ou ce n'est pas la solution.
Evidemment, le programme devra permettre plus de 6 tours si nécessaire.

Le but est de trouver une solution (si elle existe) qui permet de sortir à droite du tableau en un minimum de saut.
Il existe 3 manières de faire différente: Récursive, via un graph, ou un algorithme glouton.


Si vous avez des questions...

Voila l'illustration du problème:
Image

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Dernière édition par Fig le Dim 08/Avr/2018 19:55, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Sam 07/Avr/2018 22:16 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
Verrai ça demain, mais deja
Je ne comprends pas trop l'énoncé.... :)

Vous pouvez repeter la question (ref:les inconnus)

Donc dans ton dessin le trajet ideale serai 0145 ?
Ou 045 ?

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 08/Avr/2018 8:16 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1121
04(6)

Le bonhomme en 1 est juste là pour illustrer une position intermédiaire à la résolution du problème.

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 08/Avr/2018 11:16 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
En principe pour moi ce probleme est resolu :)

je vais attendre un peu avant de poster ma solution
histoire de pas décourager ceux qui cherchent :)

ps: j'ai choisi la solution recursive :)

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Entretiens d'embauche chez Google
MessagePosté: Dim 08/Avr/2018 14:30 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2106
hum , ça a pas l'air de concerner grand monde :)
vous avez donc une vie en dehors de Purebasic ?? :lol:

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 98 messages ]  Aller à la page Précédente  1 ... 3, 4, 5, 6, 7  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 5 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye