Podział zbioru na dwa podzbiory

Odpowiedz Nowy wątek
2019-08-10 12:56
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.
edytowany 2x, ostatnio: furious programming, 2019-08-10 20:09

Pozostało 580 znaków

2019-08-10 16:09
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)


01010100 01110101 01110100 01100001 01101010 00100000 01101110 01101001 01100101 00100000 01101101 01100001 00100000 01101110 01101001 01100011 00100000 01100011 01101001 01100101 01101011 01100001 01110111 01100101 01100111 01101111 00101110 00100000 01001001 01100011 00100000 01110011 01110100 01101111 01101110 01110100 00101110

Pozostało 580 znaków

2019-08-10 16:24
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... .

Pozostało 580 znaków

2019-08-10 21:01
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.


edytowany 3x, ostatnio: furious programming, 2019-08-10 21:03

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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