Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Общие вопросы по .NET и C# > Решение задачи Иосифа Флавия через массивы на С#

Автор: gypehot19 15.10.2016, 13:05

Господа программисты, прошу помощи! Необходимо решить задачу Иосифа Флавия через массивы.
Суть в чем: m воинов, стоящих по кругу, убивают каждого n-го. Требуется определить номер k начальной позиции воина, который останется последним.
Начала делать, но ни в какую не могу реализовать кусок с самим алгоритмом. Воины - массив из булевых переменных с начальным значением true. "Убиваем" каждого третьего (в моем условии), то бишь заменяем на false. Нужно пробегаться по массиву с первого до последнего "еще живого" до тех пор, пока не останется один true, его номер надо вытянуть.
Ничего дельного придумать не могу, помогите, пожалуйста!
Вот что у меня есть:

Код


static void Main(string[] args)
        {
            int m = 10, n = 3;
            Console.WriteLine("{0} воинов стоят по кругу, убивают каждого {1}-го; последним остается воин {2}", m, n, zad_if_mas(n, m));
         }

static int zad_if_mas(int m, int n)
        {
            int k = 0;

            bool[] knights = new bool[m];
            for (int i = 0; i < m; i++)
            {
                knights[i] = true;
            }

            while (m > 1)
            {
               // вот сюда нужно впихать сам алгоритм 
            }

            for (int i = 0; i < m; i++) // поиск номера последнего оставшегося
            {
                if (knights[i] == true)
                {
                    k = i + 1;
                }
            }
            return k;
        }

Автор: boevik 18.10.2016, 16:30

Что то в этом роде:

Код


            int currentIndexKnight = -1;
            while (m > 1)
            {
                // вот сюда нужно впихать сам алгоритм 
                int skipped = 0;
                while (skipped < n)
                {
                    currentIndexKnight = currentIndexKnight + 1 < knights.Count() ? currentIndexKnight + 1 : 0;
                    if (knights[currentIndexKnight]) skipped++;
                }
                knights[currentIndexKnight] = false;
                m--;
            }

Автор: gypehot19 19.10.2016, 16:37

смутно понимаю что в этом куске происходит... но что-то где-то явно сбивается, ибо для входных значений 10 воинов и каждого третьего выдает ответ 2, вместо 4(

Автор: boevik 19.10.2016, 22:06

Вот полный код и ответ 4

Код


        static void Main(string[] args)
        {
            int m = 10, n = 3;
            Console.WriteLine("{0} воинов стоят по кругу, убивают каждого {1}-го; последним остается воин {2}", m, n, zad_if_mas(m, n));
        }
        static int zad_if_mas(int m, int n)
        {
            bool[] knights = initArray(m);
            int currentIndexKnight = -1;
            while (m > 1)
            {
                // вот сюда нужно впихать сам алгоритм 
                int skipped = 0;
                while (skipped < n)
                {
                    currentIndexKnight = currentIndexKnight + 1 < knights.Count() ? currentIndexKnight + 1 : 0;
                    if (knights[currentIndexKnight]) skipped++;
                }
                knights[currentIndexKnight] = false;
                m--;
            }

            int k = 0;
            for (int i = 0; i < knights.Count(); i++) // поиск номера последнего оставшегося
            {
                if (knights[i] == true)
                {
                    k = i + 1;
                }
            }
            return k;
        }

        private static bool[] initArray(int m)
        {
            bool[] knights = new bool[m];
            for (int i = 0; i < m; i++)
            {
                knights[i] = true;
            }
            return knights;
        }

Автор: gypehot19 19.10.2016, 23:03

большое сердечное спасибо! теперь выдает все как положено!