Algorytm dzielenia dwukolorowej czekolady.

Odpowiedz Nowy wątek
2019-10-26 11:56
0

Witam, potrzebuje pomocy w konstrukcji rekurencji dotyczącej pewnego zadania algorytmicznego. Zadanie polega na dzieleniu czekolady na mniejsze kawałki by w efekcie otrzymać jak najmniejsze kawałki ALE

1) Czekoladę można dzielić tak jak fizyczna kostkę czekolady czyli wzdłuż bruzd pionowo i poziomo

2) Nie można dokonać dzielenia jeżeli w jego wyniku powstaną jednokolorowe kawałki(np kawałek czarny-biały już się nie podzieli bo kolejny podział to dwa kawałki tylko biały i tylko czarny)

3) Funkcja powinna zwracać tzw bilans czyli różnice kawałków których jest więcej od tych których jest mniej (np biały biały czarny, wtedy bilans równy 2-1), bilans jest liczony dla każdego podziału i na końcu zwracana jest suma bilansów.

Udało mi się napisać kod dla pierwszego dzielenia tzn jestem w stanie powiedzieć gdzie i jak (pion czy poziom) należny połamać czekoladę dla jak najmniejszego bilansu pierwszego dzielenia. Problemem jest rekurencja, nie wiem jakie zastosować warunki w przypadku sytuacji ccbb(czarny czarny bialy bialy) której już nie można podzielić natomiast cbbc już można. Wiem ze warunek końcowy rekurencji to minimum jedna kostka czarna lub biała ale nie sprawdzi się w sytuacji ccbb.

Załączam ilustracje(pierwsza z lewej to najlepszy sposob rozwiazania)
screenshot-20191026115430.png

edytowany 1x, ostatnio: Pablit0, 2019-10-26 12:04

Pozostało 580 znaków

2019-10-26 12:15
2

Wstawiłeś dwa razy ten sam obrazek, za to nie widzę ani śladu tego, do czego Tobie się udało dojść samodzielnie (nawiązanie do "Udało mi się napisać kod dla pierwszego dzielenia").


That game of life is hard to play
I'm gonna lose it anyway
The losing card I'll someday lay
So this is all I have to say
dodałem :) - Pablit0 2019-10-26 13:16

Pozostało 580 znaków

2019-10-26 12:52
1

Pokaz kod. Nagroda za rozwiazanie proponuje ustalic jako "wysokogatunkowa" czekolade.


Szacuje się, że w Polsce brakuje 50 tys. programistów
dodałem :) - Pablit0 2019-10-26 13:16

Pozostało 580 znaków

2019-10-26 13:14
0
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Divide extends Reading {
    private int wiersze;
    private int kolumny;
    private int[][] tablica_bin;
    private int R_pionowe;
    private int R_poziome;

    public int[][] reading() throws FileNotFoundException {
        int kakao = 0;
        int biala = 0;
        int bilans_pierwszy = 0;

        Scanner sc = new Scanner(new File("in.txt"));

        String zmienna_pomString = sc.nextLine();
        String[] number_split = zmienna_pomString.split(" ");

        int zmienna_pom_1 = Integer.parseInt(number_split[0]);
        kolumny = Integer.parseInt(number_split[0]);
        int zmienna_pom_2 = Integer.parseInt(number_split[1]);
        wiersze = Integer.parseInt(number_split[1]);
        tablica_bin = new int[zmienna_pom_2][zmienna_pom_1];

        for (int i = 0; i < zmienna_pom_2; i++) // 2
        {
            String temp = sc.nextLine();
            String[] splitted = temp.split("");

            for (int j = 0; j < splitted.length; j++) {

                if (splitted[j].equals("c")) {
                    kakao++;
                    tablica_bin[i][j] = 0;
                    splitted[j] = "";
                    System.out.printf(tablica_bin[i][j] + " ");
                } else {
                    biala++;
                    tablica_bin[i][j] = 1;
                    splitted[j] = "";
                    System.out.printf(tablica_bin[i][j] + " ");
                }

            }
            System.out.printf("\n");
        }

        sc.close();

        System.out.println("wiersze : " + wiersze);
        System.out.println("kolumny : " + kolumny);
        System.out.println("czarne 0 : " + kakao);
        System.out.println("białe 1 : " + biala);
        System.out.println("bilans tabliczki pierwszej " + (kakao - biala) + " lub " + (biala - kakao));
        return tablica_bin;
    }

    void printTab(int tab[][]) {
        int x = kolumny;
        int y = wiersze;

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                System.out.println(tab[i][j] + " ");
            }
            System.out.printf("\n");
        }
    }

    public void scan(int tab[][])
    {
        // sprawdzenie pionowe

        int kakao_1 = 0;
        int biala_1 = 0;
        int kakao_2 = 0;
        int biala_2 = 0;

        int bilans_1 = 0;
        int bilans_2 = 0;

        int min_bilans_pion = 0;
        int min_bilans_poz = 0;

        int min_wspol_pion = 0;
        int min_wspol_poz = 0;

        int iteracje_pionowe = 1;
        int iteracje_poziome = 1;
        int przejscia = 0;
// kolejnosc czarne1 białe1 czarn2 biale2
        int rekordy_pionowe[][] = new int[10][8];
        int rekordy_poziome[][] = new int[10][8];

        while (przejscia < kolumny - 1)
        {

            for (int i = 0; i < iteracje_pionowe; i++) {
                for (int j = 0; j < (wiersze); j++) {
                    if (tablica_bin[j][i] == 1)
                        biala_1++;
                    else
                        kakao_1++;
                }
            }

            rekordy_pionowe[przejscia][0] = kakao_1;
            rekordy_pionowe[przejscia][1] = biala_1;

            if (biala_1 > kakao_1)
                bilans_1 = (biala_1 - kakao_1);
            else
                bilans_1 = (kakao_1 - biala_1);

            if(min_bilans_pion >= bilans_1)
            {
                min_bilans_pion = bilans_1;
                min_wspol_pion = iteracje_pionowe;

            }

            for (int z = iteracje_pionowe; z < (kolumny); z++)
            {
                for (int j = 0; j < (wiersze); j++)
                {
                    if (tablica_bin[j][z] == 1)
                        biala_2++;
                    else
                        kakao_2++;
                }
            }

            rekordy_pionowe[przejscia][2] = kakao_2;
            rekordy_pionowe[przejscia][3] = biala_2;

            if (biala_2 > kakao_2)
                bilans_2 = (biala_2 - kakao_2);
            else
                bilans_2 = (kakao_2 - biala_2);

            if(min_bilans_pion >= bilans_2)
            {
                min_bilans_pion = bilans_2;
                min_wspol_pion = iteracje_pionowe;
            }

            System.out.println("Bilans_1 " + " wynosi " + bilans_1);
            System.out.println("Bilans_2 " + " wynosi " + bilans_2);
            System.out.println("===================================");

            if (iteracje_pionowe < kolumny)
                iteracje_pionowe++;

            /*
            System.out.println(rekordy_pionowe[przejscia][0] );
            System.out.println(rekordy_pionowe[przejscia][1] );
            System.out.println(rekordy_pionowe[przejscia][2] );
            System.out.println(rekordy_pionowe[przejscia][3] );
             */
            przejscia++;
             kakao_1 = 0;
             biala_1 = 0;
             kakao_2 = 0;
             biala_2 = 0;

            //for (int[] ints : tablica_bin) {

            R_pionowe =+ min_bilans_pion;
        }
        przejscia =0;
        System.out.println("=================================");
        // sprawdzanie poziome
        while (przejscia < wiersze - 1)
        {

            for (int i = 0; i < iteracje_poziome; i++) {
                for (int j = 0; j < (kolumny); j++)
                {
                    if (tablica_bin[i][j] == 1)
                        biala_1++;
                    else
                        kakao_1++;
                }
            }

            rekordy_poziome[przejscia][4] = kakao_1;
            rekordy_poziome[przejscia][5] = biala_1;

            if (biala_1 > kakao_1)
                bilans_1 = (biala_1 - kakao_1);
            else
                bilans_1 = (kakao_1 - biala_1);

            if(min_bilans_poz>= bilans_1)
            {
                min_bilans_poz = bilans_1;
                min_wspol_poz = iteracje_poziome;
            }

            for (int z = iteracje_poziome; z < (wiersze); z++)
            {
                for (int j = 0; j < (kolumny); j++)
                {
                    if (tablica_bin[z][j] == 1)
                        biala_2++;
                    else
                        kakao_2++;
                }
            }

            rekordy_poziome[przejscia][6] = kakao_2;
            rekordy_poziome[przejscia][7] = biala_2;

            if (biala_2 > kakao_2)
                bilans_2 = (biala_2 - kakao_2);
            else
                bilans_2 = (kakao_2 - biala_2);

            if(min_bilans_poz>= bilans_2)
            {
                min_bilans_poz = bilans_2;
                min_wspol_poz = iteracje_poziome;
            }

            System.out.println("Bilans_1 " + " wynosi " + bilans_1);
            System.out.println("Bilans_2 " + " wynosi " + bilans_2);

            if (iteracje_poziome < wiersze)
                iteracje_poziome++;

            przejscia++;
            kakao_1 = 0;
            biala_1 = 0;
            kakao_2 = 0;
            biala_2 = 0;

            //for (int[] ints : tablica_bin) {}
        }
        R_poziome =+ min_bilans_poz;
        System.out.println("bilans pionowy wynosi " + min_bilans_pion + " wspolrzedna " +  min_wspol_pion);
        System.out.println("ilosci czekolad pionowo");
        System.out.println("kawałek I czarne " + rekordy_pionowe[min_wspol_pion-1][0] + " białe " + rekordy_pionowe[min_wspol_pion-1][1] );
        System.out.println("kawałek II czarne " + rekordy_pionowe[min_wspol_pion-1][2] + " białe " + rekordy_pionowe[min_wspol_pion-1][3] );
        System.out.println("bilans poziomy wynosi " + min_bilans_poz + " wspolrzedna " +  min_wspol_poz);
        System.out.println("R = " + R_pionowe);
        System.out.println("ilosci czekolad poziomo");
        System.out.println("kawałek I czarne " + rekordy_poziome[min_wspol_pion-1][4] + " białe " + rekordy_poziome[min_wspol_pion-1][5] );
        System.out.println("kawałek II czarne " + rekordy_poziome[min_wspol_pion-1][6] + " białe " + rekordy_poziome[min_wspol_pion-1][7] );
        System.out.println("R = " + R_poziome);
        System.out.println("*************");

       /* if(rekordy_pionowe[min_wspol_pion-1][0] >= 1 || rekordy_pionowe[min_wspol_pion-1][1] >=1)
        {

        int[][] tab_a = new int[min_wspol_pion][wiersze];
        scan(tab_a);
        }
        if(rekordy_pionowe[min_wspol_pion-1][2] >= 1 || rekordy_pionowe[min_wspol_pion-1][3] >= 1)
        {
        int[][] tab_b = new int[kolumny - min_wspol_pion][wiersze];
        scan(tab_b);
        }
            //scan();
        //if(rekordy_poziome[min_wspol_pion-1][4] != 0 || rekordy_poziome[min_wspol_pion-1][5] != 0 )
            //scan();
        //if(rekordy_poziome[min_wspol_pion-1][6] !=0 || rekordy_poziome[min_wspol_pion-1][7] != 0 ){}
            //scan();

*/

    }
/*
    void dzialanie()
    {
        while()
    }

*/
    }
edytowany 1x, ostatnio: cerrato, 2019-10-28 09:09

Pozostało 580 znaków

2019-10-26 16:11
0

Ktoś już próbował:
https://stackoverflow.com/que[...]black-and-white-chocolate-bar


Bez pozytywnych skutków, nie umieszczałbym tematu bez wcześniejszego sprawdzenia. - Pablit0 2019-10-26 16:29
Przeczytałem, wygląda sensownie. A w ogóle, to Przeszkadza Ci ten link? - lion137 2019-10-26 16:48
Brak wyników to też wynik ... - _13th_Dragon 2019-10-29 16:00

Pozostało 580 znaków

2019-10-26 17:23
0

Jak wygląda opis wejścia, przede wszystkim maksymalne rozmiary tabliczki?


It's easy to hate code you didn't write, without an understanding of the context in which it was written.
maksymalnie 10 kolumn wiersze nie sa limitowane - Pablit0 2019-10-26 17:28

Pozostało 580 znaków

2019-10-26 17:25
0

screenshot-20191026172519.png

Pozostało 580 znaków

2019-10-29 06:11
0

Bardzo ciekawy problem.
Zastanawiam się czy próba rozwiązania go dla tablicy jednowymiarowej by pomogła?

Pozostało 580 znaków

2019-10-29 12:51
0

Coś takiego?

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef vector<char> row_t;
typedef vector<row_t> arr_t;

void count(const arr_t &tb,size_t lf,size_t rt,size_t tp,size_t bt,size_t &b,size_t &c)
{
    b=c=0;
    for(size_t y=tp;y<bt;++y) for(size_t x=lf;x<rt;++x) ++(tb[y][x]&1?c:b);
}

size_t count_diff(const arr_t &tb,size_t lf,size_t rt,size_t tp,size_t bt)
{
    size_t b,c;
    count(tb,lf,rt,tp,bt,b,c);
    return b>c?b-c:c-b;
}

bool bad_divide(const arr_t &tb,size_t lf,size_t rt,size_t tp,size_t bt)
{
    size_t b,c;
    count(tb,lf,rt,tp,bt,b,c);
    return (!b)||(!c);
}

size_t divide(const arr_t &tb,size_t lf,size_t rt,size_t tp,size_t bt)
{
    size_t ret=~0UL;
    bool found=false;
    for(size_t y=tp+1;y<bt;++y)
    {
        if((bad_divide(tb,lf,rt,tp,y))||(bad_divide(tb,lf,rt,y,bt))) continue;
        found=true;
        ret=min(ret,divide(tb,lf,rt,tp,y)+divide(tb,lf,rt,y,bt));
    }
    for(size_t x=lf+1;x<rt;++x)
    {
        if(bad_divide(tb,lf,x,tp,bt)||bad_divide(tb,x,rt,tp,bt)) continue;
        found=true;
        ret=min(ret,divide(tb,lf,x,tp,bt)+divide(tb,x,rt,tp,bt));
    }
    return found?ret:count_diff(tb,lf,rt,tp,bt);
}

int main() 
{
    size_t x,y;
    cin>>x>>y;
    arr_t tb(y,row_t(x));
    for(auto &row:tb) for(auto &cell:row) cin>>cell;
    cout<<divide(tb,0,x,0,y)<<endl;
    return 0;
}

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 2x, ostatnio: _13th_Dragon, 2019-10-29 12:52
To jest naiwne rozwiązanie, prawda? Zwyczajne backtracking z wszystkimi możliwymi podziałami? - enedil 2019-10-29 15:04
Tak, ale da się szybko i ładnie dołożyć mapę unordered_map<rect,size_t> - _13th_Dragon 2019-10-29 15:06
Ale to w dalszym ciągu daje rozwiązanie kwadratowe względem sumy długości boków tabliczki czekolady. Jesteś pewien, że nie da się szybciej? - enedil 2019-10-29 15:07
Dobre pytanie ... - _13th_Dragon 2019-10-29 15:09

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