[C++] průnik množin

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod OgyDoggy 12. 5. 2010 07:33

už jsem na to skoro přišel, jen musím někam dát podmínku, aby se mi nekontrolovali čísla, které tam už jsou
Kód: Vybrat vše
#include <iostream>
#include <fstream>

using namespace std;

const unsigned int N = 10;
int* prvniPole = new int[N];
int* druhePole = new int[N];
int* vystupniPole = new int[N];

void hledejPrvek(int serazenePole[], int neserazenePole[]){
   int leva = 0, prava = N; //první a poslední index seřazeného pole

   int stred = N/2;   //index středu seřazeného pole
   int pomoc; //do pomocné proměnné se uloží hodnota nesařezeného pole

   for(int i=0; i < N; i++){
      pomoc = neserazenePole[i];
      cout << "\n" << i << ". " << "pomocna" << " " << pomoc << " stred " << stred << endl;

      for(int j=0; j < N; j++){
         if(pomoc == serazenePole[stred]){
            cout << "nalezeno " << pomoc << " ";
         }
         else if(pomoc < serazenePole[stred]){
            prava--;
         }
         else if(pomoc > serazenePole[stred]){
            leva++;
         }
         else {
            cout << "nenalezeno " << pomoc << " ";
         }
         stred  = (leva + prava) / 2;
      }
   }
}

int main(){
   int prvniPole[] = {1,2,2,5,6,8,9,10,33,7087};
   int druhePole[] = {9,3,8,26,5,8,901,10,66,6};

   printf("\nprvni pole\n");
   for(int i = 0; i < N; i++){
      cout << i << " " << prvniPole[i] << "\n";
   }
   printf("\ndruhe pole\n");
   for(int i = 0; i < N; i++){
      cout << i << " " << druhePole[i] << "\n";
   }

   hledejPrvek(prvniPole,druhePole);
   


   printf("\n");
   system("pause");
   return 0;
}
učím se co můžu, učím se celý život, snad mi to k něčemu bude
OgyDoggy
Junior
Uživatelský avatar

Odeslat příspěvekod OgyDoggy 17. 5. 2010 17:45

dávám tady svou verzi, kterou jsem odevzdal, zajímá mě jedno, které řešení ze zde uvedených, by mělo být nejrychlejší? tady toto funguje relativně dobře na 100 000 čísel, ale u milionu... no je to nepoužitelné :/ byl by nějaký rozdíl v rychlosti, kdybych použil místo polí vector? asi ne, největší náročnost je v tom algoritmu, možná kdybych použil jiný porovnávací algoritmus, tak bych to zrychlil o něco víc.

a ještě jedna/dvě věci na které jsem ještě nepřišel, jakým způsobem mám udělat to, aby se zadával název výstupního souboru s příkazovou řádkou? vs říká něco, čemu popravdě nerozumím, a za druhé jakým způsobem se "returnuje" celé pole? jde to? když jsem to zkoušel, tak mi to dělalo nějaké chyby :(


Kód: Vybrat vše
#include <iostream>
#include <fstream>

using namespace std;

const unsigned int N = 1000000;
int prvniPole[N];
int druhePole[N];
int* pomocnePole = new int[N];


int hledejPrvek(int serazenePole[], int neserazenePole[]){
   int leva = 0, prava = N; //první a poslední index seřazeného pole
   int stred = N/2;   //index středu seřazeného pole
   int pomoc; //do pomocné proměnné se uloží hodnota nesařezeného pole

   ofstream temp;
      temp.open("vystup.txt");

   for(int i=0; i < N; i++){
      pomoc = neserazenePole[i];

      for(int j=0; j < N; j++){
         if(pomoc == serazenePole[stred]){
            temp << pomoc << endl;
            pomoc = pomocnePole[j];
            for(int k=0; k < N; k++){
               if(pomocnePole[k] == pomoc){
                  break;
               }
            }
         }
         else if(pomoc < serazenePole[stred]){
            prava--;
         }
         else if(pomoc > serazenePole[stred]){
            leva++;
         }
         else {
            cout << "nenalezeno " << pomoc << " ";
         }
         stred  = (leva + prava) / 2;
      }
   }
   return -(pomoc + 1);
}

void setridPole(int pole[], int vlevo, int vpravo) {
      int i = vlevo, j = vpravo;
      int tmp;
      int stred = pole[(vlevo + vpravo) / 2];

      while (i <= j) {
        while (pole[i] < stred){
                  i++;
        }
        while (pole[j] > stred){
                  j--;
        }
            if (i <= j) {
                  tmp = pole[i];
                  pole[i] = pole[j];
                  pole[j] = tmp;
                  i++;
                  j--;
            }
      };

     if (vlevo < j){
            setridPole(pole, vlevo, j);
     }
     if (i < vpravo){
            setridPole(pole, i, vpravo);
     }
}


int main(int argc, char *argv[]){
      system("cls");

      if(argc != 3){
         printf("chyba zadavani parametru!!!\n");
         printf("spravne zadani je 'jmeno_programu.exe' 'vstupnisoubor1.txt' 'vstupnisoubor2.txt'\n");
         printf("jmeno vystupniho souboru je automaticky nastaveno na 'vystup.txt'\n");
         system("pause");
         return -1;

      } else {

            ifstream prvniSoubor;
               prvniSoubor.open(argv[1]);
               printf("\nctu prvni soubor...");
               for(int i=0; i < N; i++){
                  prvniSoubor >> prvniPole[i];
               }

            ifstream druhySoubor;
               druhySoubor.open(argv[2]);
               printf("\nctu druhy soubor...");
               for(int j=0; j< N; j++){
                  druhySoubor >> druhePole[j];
               }

            printf("\ntridim prvni pole...");
            setridPole(prvniPole, 0, N);

            printf("\nhledam...");
            hledejPrvek(prvniPole,druhePole);


      printf("\n\nZpracoval Bretislav Kral | KRA843\n");
      system("pause");
      return 0;
   }
}
učím se co můžu, učím se celý život, snad mi to k něčemu bude
OgyDoggy
Junior
Uživatelský avatar

Odeslat příspěvekod suk 17. 5. 2010 18:13

parametry prikazovyho radku mas v poli char *argv[], argumentu tam mas int argc.
Co se tyce returnovani pole, tak misto promenny deklarujes funkci....
misto int a; mas int a();, tak stejne budes mit treba int* a();
Pokud nesouhlasíte s mým názorem, popřemýšlejte sami nad sebou. Opravdu si myslíte, že já bych se mohl mýlit?
----
You are an inspiration for a birth control...
suk
Mírně pokročilý
Uživatelský avatar

Předchozí stránka

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků