JavaRush/Java блог/Архив info.javarush/Интересная задача

20 уровень

30.08.2015
2159просмотров
27комментариев

Интересная задача

участников

Имеется четыре острова: А, B, C, D. На трех островах (A, B, C) по 2000 жителей, а на D - 2015. Можно ли через какое-то количество дней сделать, чтобы на островах B, C, D было 2000 жителей, а на А - 2015, если каждый день с одного из островов на все остальные переселяется по одному человеку.

Можно ли решить это задание? Буду благодарен за любую помощь.

Комментарии (27)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Busockiy

Уровень 27

1 сентября 2015, 22:17

«timurnav прав — задача не имеет решения, точнее решение в том, что остров А при поочерёдном переселении никогда не достигнет числа населения 2015. :)» — где здесь сказано что это поочерёдное переселение?

Grif

Уровень 11

1 сентября 2015, 22:31

Ответил чуть раньше. Если я несколько некорректно выразился в предыдущих постах, приношу свои извинения, не со злого умысла и не с целью обидеть было сказано.

Grif

Уровень 11

1 сентября 2015, 21:06

Кстати прошу прощение за код который я выложил без форматирования… в спешке…
должно было быть так:

import java.util.ArrayList;

public class TestIsland
{
    public static void main(String[] args)
    {
        int checkNumber = 2015;
        String checkName = "A";
        ArrayList<Island> islands = new ArrayList<Island>();
        for (int i = 0; i < 4; i++)
        {
            islands.add(new Island());
        }
        islandsInitializer(islands, 0, checkName, 2000);
        islandsInitializer(islands, 1, "B", 2000);
        islandsInitializer(islands, 2, "C", 2000);
        islandsInitializer(islands, 3, "D", checkNumber);
        System.out.println("***** Until the resettlement ******");
        printPeopleOnIsland(islands);
        System.out.println("***** resettlement ******");
        for (int i = 0; i < 10; i++)
        {
            relocation(islands);
            rotateIslands(islands);
            System.out.println("Passed the day: " + i);
            if (checkIsland(islands, checkName, checkNumber))
            {
                System.out.println("Islands " + checkName +
                        "population is" + checkNumber);
                break;
            }
            printPeopleOnIsland(islands);
        }
        printPeopleOnIsland(islands);
    }

    public static void rotateIslands(ArrayList<Island> list)
    {
        list.add(0, list.get(list.size() - 1));
        list.remove(list.size() - 1);
    }

    public static boolean checkIsland(ArrayList<Island> list,
                                      String checkName, int number)
    {
        boolean flag = false;
        for (int i = 0; i < list.size(); i++)
        {
            if (list.get(i).getName().equals(checkName) &&
                    list.get(i).getPe

Busockiy

Уровень 27

1 сентября 2015, 22:14

Читайте условие «если каждый день с одного из островов на все остальные переселяется по одному человеку.». Это не значит что если в первый день из острова A переселиться 3 человека на другие острова,
то на следующий день 3 человека переселится с другого острова но не острова A. Каждый день может быть один и тот же остров, к примеру каждый день будет переселение с острова A — то через 10 дней получиться
A = 1985 B = 2005 C = 2005 D = 2020. А в вашем коде каждый день идет переселение с острова на острова последовательно. Вы не правильно поняли условие задания. Проделать 4 последовательных кода можно и на листочку.

***** Until the resettlement ******
Island name is: A, the island's population 2000
Island name is: B, the island's population 2000
Island name is: C, the island's population 2000
Island name is: D, the island's population 2015
***** resettlement ******
Passed the day: 0
Island name is: D, the island's population 2016
Island name is: A, the island's population 1997
Island name is: B, the island's population 2001
Island name is: C, the island's population 2001
Passed the day: 1
Island name is: C, the island's population 2002
Island name is: D, the island's population 2013
Island name is: A, the island's population 1998
Island name is: B, the island's population 2002
Passed the day: 2
Island name is: B, the island's population 2003
Island name is: C, the island's population 1999
Island name is: D, the island's population 2014
Island name is: A, the island's population 1999
Passed the day: 3
Island name is: A, the island's population 2000
Island name is: B, the island's population 2000
Island name is: C, the island's population 2000
Island name is: D, the island's population 2015
Passed the day: 4
Island name is: D, the island's population 2016
Island name is: A, the island's population 1997
Island name is: B, the island's population 2001
Island name is: C, the island's population 2

Grif

Уровень 11

1 сентября 2015, 22:32

Я сделал универсальный код, там можно хоть 10 дней задать хоть 10000 для проведения переселений, и островов можно задать хоть 4 хоть 4000, но при 4-х островах и последовательном переселении результат будет один и тот же для каждых 4-х переселений(10 я поставил для наглядности). И я правильно понял условие задачи там ведь не сказано, что люди не могут переселяться последовательно :) Могут последовательно а могут и не последовательно… но на мой взгляд решение надо искать в возможном постоянстве, а не в случайности. Случайность очень относительна — у этой задачи может существовать множество решений, но не существует ни одного решения на которое можно рассчитывать на все 100%.

Busockiy

Уровень 27

1 сентября 2015, 22:38

Если переменную int checkNumber = 2015; вашего кода переделать на int checkNumber = 2016;
получиться вот так:

Island name is: A, the island's population 2000
Island name is: B, the island's population 2000
Island name is: C, the island's population 2000
Island name is: D, the island's population 2016
***** resettlement ******
Passed the day: 0
Island name is: D, the island's population 2017
Island name is: A, the island's population 1997
Island name is: B, the island's population 2001
Island name is: C, the island's population 2001
Passed the day: 1
Island name is: C, the island's population 2002
Island name is: D, the island's population 2014
Island name is: A, the island's population 1998
Island name is: B, the island's population 2002
Passed the day: 2
Island name is: B, the island's population 2003
Island name is: C, the island's population 1999
Island name is: D, the island's population 2015
Island name is: A, the island's population 1999
Passed the day: 3
Island name is: A, the island's population 2000
Island name is: B, the island's population 2000
Island name is: C, the island's population 2000
Island name is: D, the island's population 2016
Passed the day: 4
Island name is: D, the island's population 2017
Island name is: A, the island's population 1997
Island name is: B, the island's population 2001
Island name is: C, the island's population 2001
Passed the day: 5
Island name is: C, the island's population 2002
Island name is: D, the island's population 2014
Island name is: A, the island's population 1998
Island name is: B, the island's population 2002
Passed the day: 6
Island name is: B, the island's population 2003
Island name is: C, the island's population 1999
Island name is: D, the island's population 2015
Island name is: A, the island's population 1999
Passed the day: 7
Island name is: A, the island's population 2000
Island name is: B, the island's population 2000
I

Busockiy

Уровень 27

1 сентября 2015, 22:39

с чётными числами всё возможно.

Grif

Уровень 11

1 сентября 2015, 22:44

Ок :) Я уже сказал, всё что хотел. Элемент случайности, это элемент случайности. Хотя если разобраться с рандомом программным, то в самой глубине окажется, что эти значения генерируются не совсем случайно… или даже вовсе не случайно :) В любом случай спасибо за активное общение!

Busockiy

Уровень 27

1 сентября 2015, 22:46

точнее не с четными, а с некоторыми числами.

Busockiy

Уровень 27

1 сентября 2015, 22:47

И вам.:)

Grif

Уровень 11

1 сентября 2015, 22:51

Да :) При желании можно и в мой код вставить рандом в ниже написанном цикле для метода «rotateIslands(islands);» (вставить его во внутренний цикл, а количество циклов поставить рандомное) и тоже с ним поиграть :) Может тоже какие варианты выкинет :)

for (int i = 0; i < 10; i++)
        {
            relocation(islands);
            rotateIslands(islands);
            System.out.println("Passed the day: " + i);
            if (checkIsland(islands, checkName, checkNumber))
            {
                System.out.println("Islands " + checkName +
                        "population is" + checkNumber);
                break;
            }
            printPeopleOnIsland(islands);
        }

Busockiy

Уровень 27

1 сентября 2015, 22:59

эта задача имеет решение только если D = 2016; + 4 (2020, 2024, 2028);

Grif

Уровень 11

1 сентября 2015, 23:03

Хотите я Вам другую интересную задачку подкину? Которая точно имеет решение, решить её можно не выходя за рамки java core и само решение как на мой взгляд очень интересное может получиться :)

Busockiy

Уровень 27

1 сентября 2015, 14:16

public class Islands
{
    public static void main(String[] args)
    {

        int A = 2000;
        int B = 2000;
        int C = 2000;
        int D = 2015;
        int q = 0;
        while (true)
        {
            System.out.println(q++);
            int e = (int) (Math.random() * 4 + 1);
            if (e == 1)
            {
                A = A - 3;
                B = B + 1;
                C = C + 1;
                D = D + 1;

            }
            else if (e == 2)
            {
                B = B - 3;
                A = A + 1;
                C = C + 1;
                D = D + 1;

            }
            else if (e == 3)
            {
                C = C - 3;
                A = A + 1;
                B = B + 1;
                D = D + 1;

            }
            else if (e == 4)
            {
                D = D - 3;
                A = A + 1;
                B = B + 1;
                C = C + 1;

            }
            if (B == 2000 && C == 2000 && D == 2000 && A == 2015)
            {
                break;
            }
            if (B == 2015 && C == 2000 && D == 2000 && A == 2000)
            {
                break;
            }
            if (B == 2000 && C == 2015 && D == 2000 && A == 2000)
            {
                break;
            }

            if (A > 2030 || B > 2030 || C > 2030 || D > 2030)
            {
                 A = 2000;
                 B = 2000;
                 C = 2000;
                 D = 2015;
            }

        }
        System.out.println("Задача решена");
        System.out.println("A = " + A + " B = " + B + " C = " + C + "D = " + D );
    }
}

timurnav

Уровень 21

1 сентября 2015, 14:18

начальные значения сделай хотя бы 2004, 2004, 2004, 2003
иначе точно никогда не произойдет)

Busockiy

Уровень 27

1 сентября 2015, 14:23

и так тоже не проходит. Задача походу не решается. Остановил на 27717065 итерации.

Airo

Уровень 23

1 сентября 2015, 14:28

а попробуй не с 15, а с 16 — как timurnav решил)

Busockiy

Уровень 27

1 сентября 2015, 14:37

с 2016 решается. На 320той итерации.

public class Islands
{
    public static void main(String[] args)
    {

        int A = 2000;
        int B = 2000;
        int C = 2000;
        int D = 2016;
        int q = 0;
        while (true)
        {
            System.out.println(q++);
            int e = (int) (Math.random() * 4 + 1);
            if (e == 1)
            {
                A = A - 3;
                B = B + 1;
                C = C + 1;
                D = D + 1;

            }
            else if (e == 2)
            {
                B = B - 3;
                A = A + 1;
                C = C + 1;
                D = D + 1;

            }
            else if (e == 3)
            {
                C = C - 3;
                A = A + 1;
                B = B + 1;
                D = D + 1;

            }
            else if (e == 4)
            {
                D = D - 3;
                A = A + 1;
                B = B + 1;
                C = C + 1;

            }
            if (B == 2000 && C == 2000 && D == 2000 && A == 2016)
            {
                break;
            }
            if (B == 2016 && C == 2000 && D == 2000 && A == 2000)
            {
                break;
            }
            if (B == 2000 && C == 2016 && D == 2000 && A == 2000)
            {
                break;
            }

            if (A > 2030 || B > 2030 || C > 2030 || D > 2030)
            {
                 A = 2000;
                 B = 2000;
                 C = 2000;
                 D = 2016;
            }

        }
        System.out.println("Задача решена");
        System.out.println("A = " + A + " B = " + B + " C = " + C + "D = " + D );
    }
}

Grif

Уровень 11

1 сентября 2015, 17:06

timurnav прав — задача не имеет решения, точнее решение в том, что остров А при поочерёдном переселении никогда не достигнет числа населения 2015. :)
А вот использование рендома в строке int e = (int) (Math.random() * 4 + 1), не даёт права говорить о закономерности какого-либо решения.

public class TestIsland {
public static void main(String[] args) {
int checkNumber = 2015;
String checkName = «A»;
ArrayListislands = new ArrayList<>();
for (int i = 0; i < 4; i++) {
islands.add(new Island());
}
islandsInitializer(islands, 0, checkName, 2000);
islandsInitializer(islands, 1, «B», 2000);
islandsInitializer(islands, 2, «C», 2000);
islandsInitializer(islands, 3, «D», checkNumber);
System.out.println("***** Until the resettlement ******");
printPeopleOnIsland(islands);
System.out.println("***** resettlement ******");
for (int i = 0; i < 3000; i++) {
relocation(islands);
rotateIslands(islands);
System.out.println(«Passed the day: » + i);
if (checkIsland(islands, checkName, checkNumber)) {
System.out.println(«Islands » + checkName + «population is» + checkNumber);
break;
}
printPeopleOnIsland(islands);
}
printPeopleOnIsland(islands);
}

public static void rotateIslands(ArrayListlist) {
list.add(0, list.get(list.size() — 1));
list.remove(list.size()-1);
}

public static boolean checkIsland(ArrayListlist, String checkName, int number) {
boolean flag = false;
for (int i = 0; i < list.size(); i++) {
if (list.get(i).getName().equals(checkName) && list.get(i).getPeopleCount() == number) {
flag = true;
}
}
return flag;
}

public static void islandsInitializer(ArrayListlist, int number, String name, int peopleCount) {
list.get(number).setName(name);
list.get(numbe

Busockiy

Уровень 27

1 сентября 2015, 18:49

Почему нет? В условии сказано «каждый день с одного из островов». — Math.random возвращает число от 1 до 4 наугад(из какого острова в данный момент переселится 3 человека).

Grif

Уровень 11

1 сентября 2015, 20:52

В принципе Вы ответили на свой вопрос «почему ?» — «Math.random возвращает число от 1 до 4 наугад», с таким успехом даже решение можно не писать, а ответить так же… наугад.

Busockiy

Уровень 27

1 сентября 2015, 14:07

Спустя час не решилось…

public class Islands
{
    public static void main(String[] args)
    {

        int A = 2000;
        int B = 2000;
        int C = 2000;
        int D = 2015;
        while (true)
        {
            int e = (int) (Math.random() * 4 + 1);
            if (e == 1)
            {
                A = A - 3;
                B = B + 1;
                C = C + 1;
                D = D + 1;

            }
            else if (e == 2)
            {
                B = B - 3;
                A = A + 1;
                C = C + 1;
                D = D + 1;

            }
            else if (e == 3)
            {
                C = C - 3;
                A = A + 1;
                B = B + 1;
                D = D + 1;

            }
            else if (e == 4)
            {
                D = D - 3;
                A = A + 1;
                B = B + 1;
                C = C + 1;

            }
            if (B == 2000 && C == 2000 && D == 2000 && A == 2015)
            {
                break;
            }
            if (B == 2015 && C == 2000 && D == 2000 && A == 2000)
            {
                break;
            }
            if (B == 2000 && C == 2015 && D == 2000 && A == 2000)
            {
                break;
            }

            if (A > 2030 || B > 2030 || C > 2030 || D > 2030)
            {
                 A = 2000;
                 B = 2000;
                 C = 2000;
                 D = 2015;
            }

        }
        System.out.println("Задача решена");
        System.out.println("A = " + A + " B = " + B + " C = " + C + "D = " + D );
    }
}

timurnav

Уровень 21

1 сентября 2015, 14:11

del.

Airo

Уровень 23

1 сентября 2015, 13:55

Я думаю можно, через 15 дней!
Если, конечно, я правильно понял — алгоритм такой
1 день — с А на В, с В на С, с С на А, с D на А
2 день — с А на В, с В на С, с С на А, с D на А
…

timurnav

Уровень 21

1 сентября 2015, 13:57

с одного на все, а у тебя со всех на все :)

timurnav

Уровень 21

1 сентября 2015, 11:38

Решение сводится к тому, чтобы найти алгоритм по которому мы сможем сделать равными B, C и D.
если отбросить мишуру, у нас остается только
B=0, C=0 и D=15.
а так же возможные действия:
1. инкремент/декремент всех чисел разом
2. вычесть из одного из чисел 3, и добавить к двум оставшимся по 1
0 0 15
или
n n n+15
рассмотрим операции которыми мы можем воспользоваться.
+1 +1 -3, воспользуемся инкрементом и приведем, +4 +4 0 или 0 0 -4 (кому как нравится)
таким образом, чтобы скомпенсировать итерации и сделать сделать все три числа равными, ряд должен принять форму
n n n+k,
где k — число делящееся на 4 без остатка.
15 не делится — следовательно, задача не может быть решена

mr__lordi

Уровень 20

1 сентября 2015, 21:40

Большое спасибо добрый человек. Также благодарен все людям, которые помогли с решением.