Podział zbioru na dwa podzbiory

1

Zauważyłem że sporo zadań ćwiczeniowych jest typu => podziel zbiór cyfr od 1 do 9, z których każda cyfra występuje jednokrotnie, na dwa dowolne podzbiory i twórz z tych podzbiorów liczby na dowolny sposób, żeby spełniały jakiś warunek, na przykład liczba utworzona z pierwszego podzbioru ma równać się dwa razy liczba utworzona z drugiego podzbioru. Jak już mamy podzbiór to przeszukujemy go permutacją ale samo tworzenie podzbioru wymaga innego algorytmu. Wykorzystałem najprostszą metodę, twierdzenie matematyczne, że liczba w postaci dwójkowej daje nam dwa podzbiory wyznaczone przez miejsca jedynek i zer i gdy przejedziemy przez kolejne liczby od zera do 2^k-1 gdzie k jest licznością zbioru do podziału, to otrzymamy wszystkie rozkłady na dwa podzbiory. Ostatnio trudno o kod w Pascalu bo dominuje jeden język więc podaję go bo może się to komuś przydać na studiach jak takie zadanie na zaliczenie dostaje.

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  podzbiory = record
                podzbiór1, podzbiór2: string;
                brakPowtórzeń: boolean;
              end;

function kolejnePodzbiory(IDpodzbioru: integer; const zbiór: string): podzbiory;
var
  i, k, ileJedynek, maksJedynek, miejsce, ID, reszta: integer;
  podzb: podzbiory;
begin
  k:= length(zbiór); maksJedynek:= k div 2; ileJedynek:=0;
  podzb.podzbiór1:=''; podzb.podzbiór2:=''; ID:= IDpodzbioru;
  repeat
    reszta:= ID mod 2;
    if reszta=1
    then
    begin
      podzb.podzbiór1:=zbiór[k]+podzb.podzbiór1; ileJedynek:=ileJedynek+1;
    end
    else
      if reszta=0
      then
        podzb.podzbiór2:=zbiór[k]+podzb.podzbiór2;
    ID:= ID div 2;
    k:=k-1
  until ID = 0;
  for i := k downto 1 do
    podzb.podzbiór2:=zbiór[i]+podzb.podzbiór2;
  podzb.brakPowtórzeń:= ileJedynek<=maksJedynek;
  result:= podzb
end;

procedure TForm1.Button1Click(Sender: TObject);
const
  test='abcd';
var
  zbiory: podzbiory;
  i, pot: integer;
begin
  pot:=1;
  for i := 1 to length(test) do
    pot:= pot*2;
  for i := 1 to pot-2 do
  begin
    zbiory:= kolejnePodzbiory(i,test);
    if zbiory.brakPowtórzeń //te dwie linie kasujemy
    then                    //jeli nie zależy nam na powtórzeniach podzbiorów typu A B, B A
      memo1.Lines.Add(zbiory.podzbiór1+'  '+zbiory.podzbiór2)
  end;
end;

end.
0

Ostatnio trudno o kod w Pascalu bo dominuje jeden język

Algorytmy maja to do siebie, ze moga byc nawet w pseudokodzie a i tak kazdy jest w stanie przeczytac i zaimplementowac u siebie nawet w assemblerze (hiperbola)

2

A podobno na studiach już nie uczą niczego pascalowego, podobno pytong dominuje, bo pascal jest taki passé :D

PS: pls drogi autorze, wywal z kodu polskie nazewnictwo, tak się nie powinno pisać, a skoro to jest do nauki... .

0

Ja bym proponował, abyś nie podawał rozwiązań ”dla potomnych”, skoro Twoja wiedza jest póki co niewielka, a przede wszystkim skoro nie potrafisz pisać czytelnego i zwięzłego kodu. Poza tym masz w poważaniu dotychczasowe sugestie bardziej doświadczonych kolegów.


Znowu to samo – paskudne nazewnictwo elementów kodu, paskudne jego formatowanie, paskudne globalne funkcje wołane z poziomu zdarzeń kontrolek formularza, kod nieczytelny i nieefektywny, wypchany znakami diakrytyzowanymi. W dodatku nawet nie byłeś łaskaw usunąć zbędnych modułów z listy uses, a także komentarzy i pustych (nieużywanych) sekcji, generowanych automatycznie przez środowisko podczas tworzenia projektu. Na odp*****l, byle ”jakoś” było.

Po co w ogóle tworzysz aplikację okienkową do przetestowania tak prymitywnego algorytmu, skoro równie dobrze można stworzyć zwykły program konsolowy i wyrzucić wyniki na ekran? A tak to cała Twoja aplikacja jest formularzem z jednym przyciskiem i polem testowym do wyrzucenia wyniku. Bo nawet nie połasiłeś się na pole edycyjne służące do podania ciągu wejściowego… :/


Funkcja kolejnePodzbiory ma nazwę z tyłka, bo nie opisuje co ta funkcja robi. Identyfikatory funkcji powinny się rozpoczynać od czasownika, a wszystkie identyfikatory w kodzie pisanym w Pascalu powinny być zgodne z formatem PascalCase.

Poza tym znów masz kupę zmiennych lokalnych (zbędnych połowa), znów wynik przygotowujesz w dodatkowej zmiennej lokalnej, zamiast skorzystać z wbudowanej zmiennej Result, którą można do woli modyfikować. Algorytm wymaga testowania stanu bitów i bitowych przesunięć, ale zamiast pokazać to operatorami and i shr, używasz modulo i operatora dzielenia całkowitego. No i nadal używasz nadmiarowych drabinek ifów, zamiast chwilę pomyśleć nad uproszczeniem przepływu sterowania.

if reszta=1
then
begin
  podzb.podzbiór1:=zbiór[k]+podzb.podzbiór1; ileJedynek:=ileJedynek+1;
end
else
  if reszta=0
  then
    podzb.podzbiór2:=zbiór[k]+podzb.podzbiór2;

Ta drabinka to potwór. Testujesz stan najmłodszego bitu, czego wynikiem ZAWSZE jest 1 lub 0. Skoro wynikiem nie jest 1, to musi nim być 0 – po co więc sprawdzasz to w drugim warunku? Podpowiem – po nic, boś pisał kod na pałę, bez żadnego pomyślunku.

To samo tutaj:

pot:=1;
  for i := 1 to length(test) do
    pot:= pot*2;

Słyszałeś kiedyś o funkcji Power? Ewidentnie nie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1