Wyszukiwanie zbiorów, program w C#


(Adam Kasprzak) #1

Cześć, 

mam problem z pewnym zadaniem. Polega ono na tym, że muszę wylosować M zbiorów, a w każdym z nich będzie K-elementów od 1 do N (to już mam). Teraz muszę odnaleźć zbiór S zawierający jak najmniejszą ilość zbiorów, których elementy będą od 1 do N.

Np. mam wylosowane zbiory elementów:

2        8       0

2        0       3

1        8       4

2        5       6

3        4       6

5        4       9

9        3       5

8        1       9

0        7       2

1        8       8

 

i z tego najmniejsza ilość zbiorów których elementy są od 1 do N to:

1,8,4

2,5,6

0,7,2

9,3,5

 

liczby M i N są wprowadzane przez użytkownika, natomiast K jest to pierwiastek z N (oczywiście zaokrąglona do liczby całkowitej).

Próbuję zrobić to jakoś na tablicy wpisując do niej wylosowane liczby, ale nie wychodzi..

 

Mógłby ktoś pokierować jak to ogarnąć?

 

Póki co mam coś takiego:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace zbiory2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n;
            int m;
            int k;
            int eleZbio;
            int i, j;

            //wprowadzenie danych potrzebnych do obliczeń
            Console.WriteLine("Podaj wartość N - liczba elementów zbioru S (>100)");
            n = Convert.ToInt16(Console.ReadLine());
            Console.WriteLine("Podaj wartość M - liczba podzbiorów zbioru S (>1000)");
            m = Convert.ToInt16(Console.ReadLine());
            //obliczanie wartosci k
            k = Convert.ToInt16(Math.Round(Math.Sqrt(n)));

            //deklaracja tablicy
            int[,] wylosowaneLiczbyTab = new int[m,k];

            //start generatora liczb losowych
            Random losuj = new Random();

            for (j = 0; j < m; j++)
            {
                for (i = 0; i < k; i++)
                {
                    //losowanie
                    eleZbio = losuj.Next(n);
                    //wpisanie do tablicy
                    wylosowaneLiczbyTab[j,i] = eleZbio;
                    //wypisanie na ekranie wylosowanych liczb
                    Console.Write(Convert.ToString(eleZbio) + "\t ");
                }
                Console.WriteLine();
                Console.WriteLine();
            }

            //Array.ForEach(wylosowaneLiczbyTab, x => Console.WriteLine(x));

            int rank = wylosowaneLiczbyTab.Rank; // Will always be 2 in this case, since it's a 2D array

            int rows = wylosowaneLiczbyTab.GetUpperBound(0) - wylosowaneLiczbyTab.GetLowerBound(0) + 1;
            int cols = wylosowaneLiczbyTab.GetUpperBound(1) - wylosowaneLiczbyTab.GetLowerBound(1) + 1;

            Console.WriteLine("Array is of length [{0},{1}]", rows, cols);
     
            Console.ReadLine();



        }
    }
}

 


(Drobok) #2

Mógłbyś do tego wykorzystać algorytm minimalizacji funkcji boolowskich :arrow: 

http://edu.pjwstk.edu.pl/wyklady/jfa/scb/jfa-main-node10.html

@kostek135, rzeczywiście głupota


(kostek135) #3

Nie mam pojęcia jak powyższe może pomóc skoro to nie ten problem…


(enedil) #4

Ciekawa nomenklatura.

W matematyce zwą to czasem niewielomianowym, czyli nie istnieje taki wielomian o stałym stopniu, który będzie określał złożoność obliczeniową w notacji Wielkiego O (big O notation). Do dużej części problemów nawet złożoność liniowa jest niewystarczająca (ergo, niezadowalająca) i trzeba się uciekać do algorytmów logarytmicznych.