Harvard CS50: 3주차 과제(강의 7 및 8), 2부

Harvard 프로그래밍 기초 강의 CS50 추가 자료: 점근적 표기법, 정렬 및 검색 알고리즘 3주차 과제, 1부. 정렬 및 검색.

게임이 시작됩니다!

이제 놀 시간이에요! 대부분의 사람들은 퍼즐 게임 "태그"에 익숙합니다. 공식화하면 "태그"는 2차원 4x4 필드입니다. 이 필드에는 16개가 아니라 15개의 정사각형이 있습니다. 즉, 한 슬롯은 비어 있습니다. 각 사각형에는 번호가 매겨져 있으며 필드 내에서 수평 또는 수직으로 이동할 수 있습니다(물론 이동할 공간이 있는 경우). 목표는 왼쪽에서 오른쪽으로 위에서 아래로 1부터 15까지 숫자를 순서대로 배치하는 것입니다. 그러면 오른쪽 하단에 빈 공간이 생깁니다. 이 게임 공간에서는 임의의 타일(또는 여러 개)의 이동이 "단계"입니다. 위 사진에 표시된 조합은 이미 쌓여 있지만 빈 공간에는 12개 또는 15개의 타일을 밀어 넣을 수 있다는 점에 유의하세요. 규칙에는 타일을 대각선으로 이동하거나 플레이 보드에서 제거할 수 없다고 명시되어 있습니다. 실제로 게임을 시작하는 데는 많은 구성이 있지만(정확히 몇 개인지 셀 수 있음), 단순함을 위해 타일을 가장 큰 것부터 작은 것 순서대로 배열하고 보드 오른쪽 하단에 빈 공간을 남겨두도록 하겠습니다. . 유일한 것은 퍼즐을 풀 수 있도록 1과 2를 바꾸는 것입니다. 이제 워크벤치의 ~/ 디렉토리로 이동한 다음 /pset3/fifteen을 열고 five.c를 엽니다 . 여기에는 게임 엔진용 코드가 포함되어 있습니다. 임무는 게임에 코드를 추가하는 것입니다. 하지만 먼저 "엔진"을 컴파일해 보겠습니다(아마도 이 작업을 수행하는 방법을 이미 알고 있을 것입니다). 게임이 완료되지 않았음에도 불구하고 애플리케이션을 시작할 수 있습니다. 일반적인 터미널 창보다 더 큰 터미널 창에서 실행하는 것이 더 편리할 것입니다. 이 창은 코드 탭 중 하나 옆에 있는 녹색 더하기(+)를 클릭하고 New Terminal 을 선택하여 열 수 있습니다 . 또는 콘솔 오른쪽 상단에 있는 최대화 아이콘을 클릭하여 터미널 창을 전체 화면으로 열 수 있습니다 . 어떤 일이 어떻게든 작동한다는 것을 알 수 있습니다. 그러나 사실 대부분의 게임은 아직 작성되지 않았습니다. 그리고 여기 – 준비하세요 – 출구가 있습니다!

공부하다

five.c의 코드와 주석을 연구 하고 아래 질문에 답하세요.

1. 4x4 보드 외에 우리 엔진은 어떤 필드 크기를 허용합니까?
2. 게임 필드는 어떤 데이터 구조인가요?
3. 게임 시작 시 플레이어에게 인사하기 위해 호출되는 함수는 무엇입니까?
4. 어떤 기능을 구현해야 합니까?
5. 참고: 질문에 올바르게 대답했는지 자동 확인하려면 five.c 파일 옆에 있는 five.txt 파일을 찾아 해당 질문에 대한 답을 적어 두세요.

구현

자, 게임 구현을 시작해 보겠습니다. 우리는 작은 단계로 나아가고 있다는 것을 기억하십시오. 모든 것을 한 번에 하려고 하지 마십시오. 대신, 한 번에 하나씩 기능을 구현하고 계속 진행하기 전에 제대로 작동하는지 확인하겠습니다. 특히 게임 기능을 init(초기화), draw(그리기), move(한 걸음 내딛기), Won(승리)의 순서로 구현하는 것이 좋습니다. 디자인 결정(예: 숫자 타일 사이에 삽입할 공간 등)은 귀하의 몫입니다. 플레이 필드는 다음과 같아야 합니다. 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ 다시 한 번, 시작 위치에서 1과 2가 역순으로 위치한다는 점에 유의하세요(타일 수가 홀수인 경우 이는 클래식 4x4 필드에 적용됩니다). 타일 ​​수가 짝수이고 필드가 3x3인 경우 "가장 낮은" 타일 2개를 교체할 필요가 없습니다. 8 7 6 5 4 3 2 1 _ "태그" 구현을 테스트하려면 해당 태그를 재생해 보아야 합니다. (crtl+c 키 조합을 눌러 프로그램이 자연적으로 완료되기 전에 프로그램을 종료할 수 있다는 점을 잊지 마세요.) 잘못된 숫자를 입력해도 프로그램이 작동하는지 확인하세요. 그리고 find에 대한 입력을 자동화한 것처럼 게임의 "연습"도 자동화할 수 있다는 점을 기억하십시오. 실제로 ~cs50/pset3 폴더에는 3x3.txt 및 4x4.txt 파일이 있으며 , 여기에는 3x3 및 4x4 필드에서 승리하기 위한 모든 단계 시퀀스가 ​​포함되어 있습니다. 예를 들어 첫 번째 파일을 사용하여 프로그램을 테스트하려면 다음 명령을 실행하십시오. ./fifteen 3 < ~cs50/pset3/3x3.txt 애니메이션 속도를 높이는 데 필요한 인수를 설정하십시오. 일반적으로 원하는 경우 언제든지 게임을 변경할 수 있습니다. 색상을 포함한 "ANSI 이스케이프 시퀀스"를 즐겨보세요. Clear 구현을 살펴보고 http://isthe.com/chongo/tech/comp/ansi_escapes.html을 확인하여 새로운 트릭을 알아보세요. 원한다면 자신만의 함수를 작성하거나 우리가 작성한 함수의 프로토타입을 변경하세요. 유일한 제한은 main 함수의 논리를 변경하지 않는다는 것입니다. 그렇지 않으면 프로그램이 올바르게 작동하는지 확인하기 위해 일부 자동 테스트를 적용할 수 없습니다. 특히, main은 사용자가 퍼즐을 푼 경우에만 0을 반환해야 합니다. 모든 오류 옵션에 대해 0이 아닌 값을 반환해야 합니다. 오류가 발생하면 우리에게 편지를 보내주십시오. 음, CS50 보조자가 준비한 애플리케이션 구현을 가지고 놀고 싶다면 다음 명령을 실행하십시오. ~cs50/pset3/fifteen 자동 퍼즐 해결 기능을 갖춘 더 멋진 구현을 보려면 프로그램의 "Hacker" 버전을 확인하십시오. ~cs50/hacker3/fifteen 게임 창에 숫자를 입력하는 대신 GOD라는 단어를 입력하세요.. 좋아요, 그렇죠? 공식적으로 check50을 사용하여 프로그램의 정확성을 확인하려면 check50에서는 플레이 필드의 빈 공간이 0으로 채워져 있다고 가정합니다. 다른 값을 선택한 경우 올바른 확인을 위해 0으로 바꾸십시오. 또한 check50에서는 보드 [열] [행]이 아닌 [행] [열] 순서로 보드 필드를 인덱싱한다고 가정합니다. check50 2015.fall.pset3.fifteen fifteen.c

Fifteen 게임 기능 구현에 대해 자세히 알아보세요.

• init(초기화)
• 그리다
• 움직이다 (한 걸음 내딛다)
• 이겼다(승리)

초기화

이 기능에서는 경기장을 소개합니다. 이를 위해 우리는 2차원 정수 배열을 사용합니다. 배열 차원은 MAX x MAX입니다. 여기서 MAX는 필드의 행이나 열에 들어갈 수 있는 최대 타일 수를 나타내는 상수입니다. 따라서 int board[MAX][MAX] 변수를 정의해야 합니다 . 그러나 경기장의 크기는 사용자에 의해 결정된다는 점을 기억하십시오. 따라서 사용자가 입력해야 하는 보드 크기를 나타내는 변수를 정의해야 합니다. 이것은 int d 입니다 . 여기서 d는 보드 치수이고, d <= MAX입니다. 그러나 C에서는 배열의 크기를 변경할 수 없으므로 최대 크기를 결정해야 합니다. init 에서는 보드에 값을 넣어야 합니다. 아직 작업해 본 적이 없다면 2차원 배열에 대해 자세히 읽어보세요. 즉, 두 개의 인덱스가 있는데 첫 번째는 행 번호를 나타내고 두 번째는 열 번호를 나타냅니다. 우리 문제에서는 최대 숫자로 시작하여 d = 3(“Eights”)인 경우 1과 빈 모서리로 끝납니다. 여전히 "태그"가 있으면 1과 2를 바꿉니다. 빈 공간은 어떻게 할까요? 우리의 배열은 정수로 구성되어 있으므로 공백은 정수로 채워져야 합니다. 따라서 빈 타일(또는 실제 게임의 경우 타일이 없는 경우)을 초기화하려면 정수를 선택해야 합니다. 루프를 사용하여 게임 보드를 초기화하고 시작 타일 세트로 채울 수 있습니다. 우리는 인덱스 i와 j를 반복합니다. 여기서 board[i][j] 는 행 번호 i와 열 번호 j에 있는 타일입니다. 우리는 내림차순으로 보드를 채웁니다. (빈 타일 제외) 타일의 개수가 홀수이면 1과 2를 바꿉니다.

그리다

이 함수는 플레이필드의 현재 상태를 인쇄해야 합니다. 한 자리 또는 두 자리 숫자의 값을 가질 수 있으므로 숫자 1-9 뒤에 아름다운 형식을 지정하려면 함수에서 공백( #s )을 인쇄해야 합니다. 이는 %2d 자리 표시자를 사용하여 수행할 수 있습니다 . printf (“%2d”, board[i][j]); 또한 빈 셀을 잊지 마세요. 이를 나타내는 문자를 선택하십시오(이 예에서는 밑줄입니다). 그리기 기능은 빈 셀에 도달하자마자 이 문자를 그려야 합니다. 따라서 루프는 다음과 같습니다. for каждой строки for каждого element строки print meaning и пробел print новую строку 그리기 함수가 타일을 화면에 그리는 순서는 init 함수에 정의된 배열의 순서를 반영해야 한다는 점을 기억하세요 .

이동하다

경기장을 초기화하고 초기 타일 위치를 그린 후에는 사용자가 타일 위치를 편집할 수 있도록 허용해야 합니다. 즉, 이동할 수 있어야 합니다. 따라서 Fifteen.c 에서 프로그램은 사용자로부터 출력을 받아 게임 보드를 만든 다음 이동 함수를 호출하고 사용자가 이동하려는 타일을 알려줍니다. 주의하세요: 함수를 보드(배열)의 위치가 아닌 타일의 숫자에만 적용하는 것입니다. 따라서 타일의 실제 위치를 찾아야 합니다. 또한 가능한 경우에만 사용자가 타일을 이동할 수 있도록 허용해야 합니다. 위 그림에서는 타일 번호 2, 5, 8만 이동할 수 있습니다. 이를 어떻게 결정합니까? 빈 타일의 가치로. 따라서 이동 기능은 다음과 같이 작동합니다.

• 사용자가 이동하려는 타일 번호를 수락합니다.
• 이 타일의 배열(경기장)에서 위치를 찾습니다.
• 빈 타일의 위치를 ​​기억합니다.
• 사용자가 이동하려는 타일 옆에 빈 타일이 있으면 배열에서 교체됩니다.

이겼다

이 기능은 각 사용자 단계 후에 게임이 종료되었는지 확인합니다. 타일의 순서가 올바른 경우(오른쪽 하단 모서리에 있는 빈 타일의 위치 포함) true를 반환합니다. 이 경우 프로그램이 종료될 수 있습니다. 타일이 여전히 흩어져 있는 경우 함수는 false를 반환하고 고삐를 move 함수에 전달합니다 . 검사를 조직하는 방법은 무엇입니까? 보드를 초기화하고 그리는 경우와 마찬가지로 두 개의 중첩된 for 루프를 사용합니다. 예를 들어, 배열의 각 후속 숫자가 이전 숫자보다 커야 한다는 조건을 설정할 수 있습니다. 빈 타일에 어떤 값이 적혀 있는지 확인하세요. 또는 다른 방법 - 카운터를 사용하여 모든 타일이 제자리에 있는지 확인하고, 처리할 수 있고 타일을 얻기 위한 공식을 작성하세요. 귀하의 실험에 행운이 있기를 바랍니다!

코드를 검증하고 점수를 받는 방법

주목! 작업의 정확성만 확인하는 것이 중요하다면 cs50check를 사용하세요. edx 플랫폼에서 성적을 받으려면 아래 설명된 절차를 따르세요. 이 절차에서는 동일한 cs50check를 사용하여 작업을 확인합니다. 유일한 차이점은 결과를 기억하고 전체 점수를 계산한다는 것입니다.

1. CS50 IDE 에 로그인
2. 파일 브라우저가 있는 CS50 IDE 왼쪽 상단 근처 (터미널 창이 아님)에서 pset3 디렉토리를 마우스 오른쪽 버튼으로 클릭하고 다운로드를 클릭합니다 . 브라우저가 pset3.tar.gz 아카이브를 다운로드한 것을 볼 수 있습니다 .
3. 별도의 창이나 탭에서 CS50 에 로그인하세요.
4. 화면 왼쪽 상단에 있는 제출 아이콘을 클릭하세요.
5. 왼쪽 폴더 목록에서 Problem Set 3 디렉토리를 클릭한 다음 Upload New Submission 버튼을 클릭합니다. 그것은 오른쪽에 있습니다.
6. 나타나는 화면에서 파일 추가 ... 버튼을 클릭하십시오. 컴퓨터에서 파일을 선택하는 창이 열립니다.
7. pset3.tar.gz를 저장한 폴더로 이동합니다. 다운로드 폴더 나 브라우저가 기본적으로 파일을 저장하는 위치에 있을 가능성이 높습니다 . pset3.tar.gz 를 찾으면 한 번 클릭하여 선택한 다음 Open 을 클릭하세요 .
8. 업로드 시작 을 클릭합니다 . 파일이 CS50 서버 에 업로드됩니다 .
9. 나타나는 화면에 선택한 파일 없음 창이 표시되어야 합니다 . 마우스 커서를 왼쪽으로 움직이면 다운로드된 파일 목록이 표시됩니다. 확인하려면 각각을 클릭하세요. 확실하지 않은 부분이 있으면 동일한 단계를 반복하여 파일을 다시 업로드할 수 있습니다. 2016년 말까지 원하는 만큼 이 작업을 수행할 수 있습니다.