none
C# помогите переделать циклы в рекурсию. RRS feed

  • Вопрос

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

    Задача:

    Нужно создать список двухмерных массивов (квадратных матриц). Но, в этот список должны входить ВСЕ возможный варианты матриц (в последствии буду исключать матрицы, которые имеют строки или столбцы заполненные нулями). Матрицы содержат только цифры 0 и 1. (В последствии там будут и другие цифры).

    Сейчас реализовал так:

    Создаю одномерный массив заполненный значениями от 1 до «размер матрицы». Например, для матрицы 2х2 создаю одномерный массив, который содержит числа 01,10,11. Потом по очереди заполняю 1-ю строку и вторую строку значениями из этого массива.

    int[] arr1D;
    List<int[]> listArr1D = new List<int[]>();
    int q;
    int f;
    int maxLength1D;
    int strLength;
    int f_rang;
    q = 2;
    //f = 4;
    f_rang = 2;// Convert.ToInt32(Math.Sqrt(f));
    maxLength1D = Convert.ToInt32(Math.Pow(q, f_rang) - 1);
    arr1D = new int[f_rang];
    
    string str_max;
    //создание одномерного массива заполненного нужными числами.
    for (int maxL = 0; maxL <= maxLength1D; maxL++)
    {
        arr1D = new int[f_rang];
        str_max = Convert.ToString(maxL, q);
        str_max = str_max.PadLeft(f_rang, '0');
        strLength = str_max.Length;
    
        for (int i = 0; i < strLength; i++)
        {
            arr1D[i] = Convert.ToInt32(str_max.Substring(strLength - 1 - i, 1));
        }
        listArr1D.Add(arr1D);
    }
    
    int[,] arr2D, arr2D_2;
    List<int[,]> listArr2D = new List<int[,]>();
    arr2D = new int[f_rang, f_rang];
    //вот заполнение матрицы!!!
    for (int L1D = 1; L1D < listArr1D.Count; L1D++) //запись рядка матрицы
    {
    arr2D = new int[f_rang, f_rang];
    for (int x = 0; x < f_rang; x++)
    {
        arr2D[0, x] = listArr1D[L1D][x];
    }
        //
            arr2D_2 = копия2D(arr2D);
    
            for (int L1D_2 = 1; L1D_2 < listArr1D.Count; L1D_2++) //запись рядка матрицы
            {
    for (int x_2 = 0; x_2 < f_rang; x_2++)
    {
        arr2D_2[1, x_2] = listArr1D[L1D_2][x_2];
    }
    //
    
    // Тут такой же код если матрица большего размера, чем 2 х 2.
    
    //
    listArr2D.Add(копия2D(arr2D_2));
      }
    
    //       
    }
    

    Как переделать код после строчки «//вот заполнение матрицы!!!» в рекурсию, чтобы можно было вызывать эту рекурсию для любого размера матрицы?

Ответы

  • using System;
    using System.Collections.Generic;
    using System.Linq;
    internal static class Test{
        private static void Main(){
            foreach(int[,] matrix in GenAllMatrix(3,3)){
                Console.WriteLine("{0}|{1}|{2}",matrix[0,0],matrix[0,1],matrix[0,2]);
                Console.WriteLine("{0}|{1}|{2}",matrix[1,0],matrix[1,1],matrix[1,2]);
                Console.WriteLine("{0}|{1}|{2}",matrix[2,0],matrix[2,1],matrix[2,2]);
                Console.WriteLine("-----");
            }
            Console.ReadKey(true);
        }
        private static IEnumerable<int[,]> GenAllMatrix(int maxValue,int size){
            int[,] matrix=new int[size,size];
            yield return (int[,])matrix.Clone();
            for(int i=size*size-1;i>=0;--i){
                int x=i/size;
                int y=i%size;
                matrix[x,y]=(matrix[x,y]+1)%maxValue;
                if(matrix[x,y]!=0){
                    yield return (int[,])matrix.Clone();
                    i=size*size;
                }
            }
        }
    }

    • Помечено в качестве ответа sg6336 23 мая 2013 г. 18:49

Все ответы

  • using System;
    using System.Collections.Generic;
    using System.Linq;
    internal static class Test{
        private static void Main(){
            foreach(int[,] matrix in GenAllMatrix(3,3)){
                Console.WriteLine("{0}|{1}|{2}",matrix[0,0],matrix[0,1],matrix[0,2]);
                Console.WriteLine("{0}|{1}|{2}",matrix[1,0],matrix[1,1],matrix[1,2]);
                Console.WriteLine("{0}|{1}|{2}",matrix[2,0],matrix[2,1],matrix[2,2]);
                Console.WriteLine("-----");
            }
            Console.ReadKey(true);
        }
        private static IEnumerable<int[,]> GenAllMatrix(int maxValue,int size){
            int[,] matrix=new int[size,size];
            yield return (int[,])matrix.Clone();
            for(int i=size*size-1;i>=0;--i){
                int x=i/size;
                int y=i%size;
                matrix[x,y]=(matrix[x,y]+1)%maxValue;
                if(matrix[x,y]!=0){
                    yield return (int[,])matrix.Clone();
                    i=size*size;
                }
            }
        }
    }

    • Помечено в качестве ответа sg6336 23 мая 2013 г. 18:49
  • Сколько нужно времени, что бы научиться писать такой код?
  • Лично мне для этого потребовалось несколько лет.