kwadratowy logiczna roztwór

Question

Pytanie: podano liczbę całkowitą N, drukowanie numery od 1 do n tak:

n = 4

wyniku:

01 02 03 04 
12 13 14 05 
11 16 15 06 
10 09 08 07 

Jak czy rozwiązujesz go (oprócz rozwiązania podanego w linku poniżej)?

http://www.programmersheaven.com/mb/CandCPP/81986/81986/problem-in-making-ap-c++-program/?S=B20000

szukam w innym kierunku. Do tej pory staram się dowiedzieć, czy mogę uzyskać uporządkowaną listę pozycji, które muszę wypełnić.

Oto, na co patrzę: czy istnieje sposób na uzyskanie "fdisp", aby rozwiązać problem w ten sposób, zamiast "chodzić" w matrycy?

matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] 
n = len(matrix) 

# final disposition wrote by hand: how to get it for arbitrary n? 
fdisp = [(0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3), (3,2), 
     (3,1), (3,0), (2,0), (1,0), (1,1), (1,2), (2,2), (2,1)] 

for val,i in enumerate(fdisp): 
    matrix[i[0]][i[1]] = val + 1 

def show_matrix(matrix, n): 
    for i,l in enumerate(matrix): 
     for j in range(n): 
      print "%d\t" % matrix[i][j], 
     print 

show_matrix(matrix, n) 

Answer 1

Choć Twój przykład jest w Pythonie i jest w Javie, myślę, że powinieneś być w stanie śledzić logikę:

public class SquareTest { 

public static void main(String[] args) { 
    SquareTest squareTest = new SquareTest(4); 
    System.out.println(squareTest); 
} 

private int squareSize; 
private int[][] numberSquare; 
private int currentX; 
private int currentY; 
private Direction currentDirection; 

private enum Direction { 
    LEFT_TO_RIGHT, RIGHT_TO_LEFT, TOP_TO_BOTTOM, BOTTOM_TO_TOP; 
}; 

public SquareTest(int squareSize) { 
    this.squareSize = squareSize; 
    numberSquare = new int[squareSize][squareSize]; 
    currentY = 0; 
    currentX = 0; 
    currentDirection = Direction.LEFT_TO_RIGHT; 
    constructSquare(); 
} 

private void constructSquare() { 
    for (int i = 0; i < squareSize * squareSize; i = i + 1) { 
     numberSquare[currentY][currentX] = i + 1; 
     if (Direction.LEFT_TO_RIGHT.equals(currentDirection)) { 
      travelLeftToRight(); 
     } else if (Direction.RIGHT_TO_LEFT.equals(currentDirection)) { 
      travelRightToLeft(); 
     } else if (Direction.TOP_TO_BOTTOM.equals(currentDirection)) { 
      travelTopToBottom(); 
     } else { 
      travelBottomToTop(); 
     } 
    } 
} 

private void travelLeftToRight() { 
    if (currentX + 1 == squareSize || numberSquare[currentY][currentX + 1] != 0) { 
     currentY = currentY + 1; 
     currentDirection = Direction.TOP_TO_BOTTOM; 
    } else { 
     currentX = currentX + 1; 
    } 
} 

private void travelRightToLeft() { 
    if (currentX - 1 < 0 || numberSquare[currentY][currentX - 1] != 0) { 
     currentY = currentY - 1; 
     currentDirection = Direction.BOTTOM_TO_TOP; 
    } else { 
     currentX = currentX - 1; 
    } 
} 

private void travelTopToBottom() { 
    if (currentY + 1 == squareSize || numberSquare[currentY + 1][currentX] != 0) { 
     currentX = currentX - 1; 
     currentDirection = Direction.RIGHT_TO_LEFT; 
    } else { 
     currentY = currentY + 1; 
    } 
} 

private void travelBottomToTop() { 
    if (currentY - 1 < 0 || numberSquare[currentY - 1][currentX] != 0) { 
     currentX = currentX + 1; 
     currentDirection = Direction.LEFT_TO_RIGHT; 
    } else { 
     currentY = currentY - 1; 
    } 
} 

@Override 
public String toString() { 
    StringBuilder builder = new StringBuilder(); 
    for (int i = 0; i < squareSize; i = i + 1) { 
     for (int j = 0; j < squareSize; j = j + 1) { 
      builder.append(numberSquare[i][j]); 
      builder.append(" "); 
     } 
     builder.append("\n"); 
    } 

    return builder.toString(); 
} 
} 

Answer 2

Innym sposobem, aby to zrobić, tym razem w języku C#:

int number = 9; 
var position = new { x = -1, y = 0 }; 
var directions = new [] { 
    new { x = 1, y = 0 }, 
    new { x = 0, y = 1 }, 
    new { x = -1, y = 0 }, 
    new { x = 0, y = -1 } 
}; 

var sequence = (
    from n in Enumerable.Range(1, number) 
    from o in Enumerable.Repeat(n, n != number ? 2 : 1) 
    select o 
).Reverse().ToList(); 

var result = new int[number,number]; 

for (int i = 0, current = 1; i < sequence.Count; i++) 
{ 
    var direction = directions[i % directions.Length];  

    for (int j = 0; j < sequence[i]; j++, current++) 
    { 
     position = new { 
      x = position.x + direction.x, 
      y = position.y + direction.y 
     }; 

     result[position.y, position.x] = current; 
    } 
} 

Answer 3

Znalazłem sposób. Teraz muszę go trochę poprawić, zwłaszcza że muszę znaleźć czystszy sposób na zbudowanie "fdisp". n = 5

dim = n 
pos = (0, -1) 
fdisp = [] 
squares = n % 2 == 0 and n/2 or n/2 + 1 

for _ in range(squares): 
    pos = (pos[0], pos[1] + 1) 
    fdisp.append(pos) 

    fdisp += [(pos[0],pos[1]+i) for i in range(1, dim)] 
    pos = fdisp[-1] 
    fdisp += [(pos[0]+i,pos[1]) for i in range(1, dim)] 
    pos = fdisp[-1] 
    fdisp += [(pos[0],pos[1]-i) for i in range(1, dim)] 
    pos = fdisp[-1] 
    fdisp += [(pos[0]-i,pos[1]) for i in range(1, dim - 1)] 
    pos = fdisp[-1] 
    dim = dim - 2 

matrix = [[0] * n for i in range(n)] 

for val,i in enumerate(fdisp): 
    matrix[i[0]][i[1]] = val + 1 

def show_matrix(matrix, n): 
    for i,l in enumerate(matrix): 
     for j in range(n): 
      print "%d\t" % matrix[i][j], 
     print 

show_matrix(matrix, n) 

Answer 4

Oto inne podejście. Polega na wykryciu, że ruchy, które robisz, przechodzą cyklicznie: w prawo, w dół, w lewo, w górę, w prawo, ... Co więcej, liczba ruchów idzie: 3 w prawo, 3 w dół, 3 w lewo, 2 w górę, w prawo , 1 w dół, 1 w lewo. Więc bez dalszych ceregieli, zakoduję to w Pythonie.

pierwsze, będę korzystać z niektórych itertools i trochę numpy:

from itertools import chain, cycle, imap, izip, repeat 
from numpy import array 

Cykl kierunkach pomiędzy: prawo, w dół, w lewo, w górę, w prawo, ...:

directions = cycle(array(v) for v in ((0,1),(1,0),(0,-1),(-1,0))) 

(I Używam tutaj tablic numpy, dzięki czemu mogę łatwo dodawać razem wskazówki. Krotki nie ładnie się ładują.)

Następnie kilka razy przenieść odlicza od n-1 do 1, powtarzając każdą liczbę razy, a pierwszy numer trzy razy:

countdown = chain((n-1,), *imap(repeat, range(n-1,0,-1), repeat(2))) 

Więc teraz moja sekwencja kierunków mogą być tworzone powtarzając każdy kolejny kierunek przez sparowany numer w odliczaniu:

dirseq = chain(*imap(repeat, directions, countdown)) 

aby mój ciąg indeksów, mogę tylko podsumować tę sekwencję, ale (AFAIK) Python nie przewiduje takiej metody, więc niech szybko rzucić jedną razem:

def sumseq(seq, start=0): 
    v = start 
    yield v 
    for s in seq: 
    v += s 
    yield v 

teraz do generowania oryginalnej tablicy, można wykonać następujące czynności:

a = array(((0,)*n,)*n) # n-by-n array of zeroes 
for i, v in enumerate(sumseq(dirseq, array((0,0)))): 
    a[v[0], v[1]] = i+1 
print a 

który dla n = 4, otrzymujemy:

[[ 1 2 3 4] 
[12 13 14 5] 
[11 16 15 6] 
[10 9 8 7]] 

, a dla N = 5 daje :

[[ 1 2 3 4 5] 
[16 17 18 19 6] 
[15 24 25 20 7] 
[14 23 22 21 8] 
[13 12 11 10 9]] 

Podejście to można uogólnić do prostokątnych siatek; Zostawiam to jako ćwiczenie dla czytelnika;)

Answer 5

Rozwiązałem twój problem używając C++. Nie wiem, czy to będzie dla ciebie pomocne. Ale opublikowanie go. Jeśli to zadziała, będzie to dla ciebie przyjemność.

Oto kod:

#include<iostream> 
    #include<string.h> 
    using namespace std; 

    bool valid(int n,int r,int c) 
    { 
     if(r>=1 && r<=n && c>=1 && c<=n) 
      return true; 
     return false; 
    } 


    int main() 
    { 
     pair<int,int>d1,d2,d3,d4,temp; 
     d1 = make_pair(0,1); 
     d2 = make_pair(1,0); 
     d3 = make_pair(0,-1); 
     d4 = make_pair(-1,0); 
     /**********************direction******************************/ 

     int n, i, j, counter=1, newR = 1, newC = 0, direction = 4; 
     bool changeDir=true; 
     /**************************variables*************************/ 

     cin>>n; 
     int arr[n+1][n+1]; 
     int visited[n+1][n+1]; 
     /*************************arrays********************************/ 

     memset(visited,0,sizeof(visited)); 
     memset(arr,0,sizeof(arr)); 
     /***************initializing the array**************************/ 

     while(counter<=n*n) 
     { 
      if(direction==1 && changeDir) 
      { 
       temp = make_pair(d2.first,d2.second); 
       direction=2; 
       changeDir=false; 
      } 
      else if(direction==2&& changeDir) 
      { 
       temp = make_pair(d3.first,d3.second); 
       direction=3; 
       changeDir=false; 
      } 
      else if(direction==3&& changeDir) 
      { 
       temp = make_pair(d4.first,d4.second); 
       direction=4; 
       changeDir=false; 
      } 
      else if(direction==4&& changeDir) 
      { 
       temp = make_pair(d1.first,d1.second); 
       direction=1; 
       changeDir=false; 
      } 
      while(counter<=(n*n) && !changeDir) 
      { 
       newR =newR+temp.first; 
       newC=newC+temp.second; 
       if(valid(n,newR,newC) && !visited[newR][newC]) 
       { 
        arr[newR][newC]=counter; 
        visited[newR][newC]=1; 
        counter++; 
       } 
       else 
       { 
        newR-=temp.first; 
        newC-=temp.second; 
        changeDir=true; 
        break; 
       } 
      } 
     } 
     for(i=1;i<=n;i++) 
     { 
      for(j=1;j<=n;j++) 
      { 
       if(arr[i][j]<10) 
        cout<<0; 
       cout<<arr[i][j]<<" "; 
      } 
      cout<<endl; 
     } 
     return 0; 
    } 

Oto wynik gdzie N = 5:

01 02 03 04 05 
16 17 18 19 06 
15 24 25 20 07 
14 23 22 21 08 
13 12 11 10 09 

Dziękuję.