Algorytm dzielenia dwukolorowej czekolady.

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

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").

1

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

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()
    }

*/
    }
0

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

0

screenshot-20191026172519.png

0

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

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;
}

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