Gradina zoologica

Rezolvarea problemelor de matematica prin realizarea unor programe.
Pollux
junior
junior
Mesaje: 121
Membru din: 11 Mai 2012, 22:21

Gradina zoologica

Mesaj de Pollux » 27 Dec 2012, 18:25

Intr-o gradina zoologica sunt n colivii cu papagali.Omaimuta jucausa trece prin fata coliviilor si deschide toate usile acestora.Apoi,se intoarce si inchide usile din noua in doua(incepand cu prima colivie).Jocul sau se reia mergand din trei in trei colivii,inchizand usile deschise si deschizandu-le pe cele inchise.Apoi maimuta merge din patru in patru,din cinci in cinci,s.a.m.d. in final din n in n colivii,incepand de fiecare data cu prima colivie.Sa se afiseze coliviile ramase deschise.

Exemplu. Pentru un numar de 10 colivii vor ramane deschise coliviile 2,5,10.

Va multumesc anticipat!

gixgex
junior
junior
Mesaje: 206
Membru din: 17 Apr 2012, 20:54
Localitate: Iasi

Mesaj de gixgex » 27 Dec 2012, 22:47

nu stiu daca o sa te ajute aceasta informatie in rezolvarea problemei , dar numarul coliviilor ramase este egal cu nr patratelor perfecte pan ala n . cred ca acele colivii trebuie sa aiba numar impar de divizori

ps:nu am stat sa "banez" ideeile de mai sus, dar poti lua tu niste cazuri sa vezi daca am gresit

Zeus
senior
senior
Mesaje: 424
Membru din: 10 Mai 2012, 17:22

Mesaj de Zeus » 27 Dec 2012, 22:58

Eu cred ca tb sa ne dai niste restrictii ptr n. Tb sa ne zici sursa problemei. In ce timp sa ruleze programul limita de memorie si eventual complexitatea dorita. Eu unu` nu te pot ajuta fara acest minim de informatii care le cer!!!

xor_NTG
senior
senior
Mesaje: 670
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 27 Dec 2012, 23:27

Eu abordez problema intr-o maniera destul de simplista: un vector care retine componente de 0 si 1 in functie de cum e colivia la un moment dat (inchisa respectiv deschisa). Un for imbricat cu o variabila auxiliara de marire a pasului de crestere (din 2 in 2, din 3 in 3, etc) rezolva problema destul de usor: daca in componenta verificata la un moment dat se afla valoarea 0, aceasta se modifica in 1 si invers.

Sunt de acord cu afirmatiile domnului Zeus legate de restrictiile pentru n. Eu am considerat n ca avand o valoare maxima egala cu 1000 dar totusi trebuia precizat. Dar nu cred ca aceste informatii sunt extrem de importante in acest context, mai important este algoritmul, zic eu.

Programul e testat doar pe cateva exemple mici, printre care si cel din problema:

Cod: Selectaţi tot

#include<iostream>
using namespace std;
int v&#91;1000&#93;, i,n, k=2;
int main&#40;&#41;
&#123;
    cout<<"n=";
    cin>>n;
    for&#40;i=1; i <= n; i++&#41;
    &#123;
        v&#91;i&#93; = 1;
    &#125;
   for&#40;int j=k; j<=n; j++&#41;
   &#123;
     for&#40;i=1; i<=n; i = i+k&#41;
     &#123;
         if&#40;v&#91;i&#93;==1&#41;
         &#123;
             v&#91;i&#93; = 0;
         &#125;
         else v&#91;i&#93; = 1;
     &#125;
     k++;
   &#125;

    for&#40;i=1; i<=n; i++&#41;
    &#123;
          if&#40;v&#91;i&#93;==1&#41;
          &#123;
              cout<<i<<" ";
          &#125;
    &#125;
    return 0;
&#125;
Evident, e foarte posibil ca domnul Zeus sa spuna ca nu e eficient. Sunt constient de asta. Se poate omite primul for si modificarea valorilor de comparatie in forul imbricat. Asta ar insemna ca o colivie deschisa este marcata cu 0 iar una inchisa este marcata cu 1. Asta ar fi un fel de optimizare. Nu (cred) ca e cazul in acest context sa facem optimizari. No offense.

:wink:

Pollux
junior
junior
Mesaje: 121
Membru din: 11 Mai 2012, 22:21

Mesaj de Pollux » 28 Dec 2012, 00:15

Enuntul problemei a fost scris exact cum se da in carte,nu se precizeaza care ar fi limitele intre care sa se incadreze acel n.Problema este luata dintr-o culegere de informatica cu probleme pentru clasele IX-XI,autoarea fiind Carmen Popescu iar editura este L&S info-mat.

Multumesc pentru mesajele trimise si pentru timpul acordat :D

xor_NTG
senior
senior
Mesaje: 670
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 28 Dec 2012, 12:52

Pollux: ai inteles algoritmul de mai sus, sau doar l-ai luat ca fiind in regula?

E posibil ca Zeus sa spuna ca nu trebuia sa iti dau programul direct, ci sa te las sa te mai gandesti...sa iti dau niste idei, conexiuni, etc...si tind sa cred ca ar fi avut dreptate. :!:

Pollux
junior
junior
Mesaje: 121
Membru din: 11 Mai 2012, 22:21

Mesaj de Pollux » 28 Dec 2012, 13:02

Nu-i problema,incerc sa inteleg metodele prin care rezolvati problemele.Sunt sigur ca se vede ca nu prea stiu sa rezolv individual acest tip de probleme,insa intampin ceva dificultati la vectori(nu prea am inteles acest capitol la scoala).

Scrie răspuns