알고리즘 (후판정 루프·전판정 루프)

후쿠시마 선생님의 「기본 정보 기술자 시험 오후·알고리즘편」을 공부하고 있어, 조금 이해에 시간이 걸렸던 곳

<「(p.49) 루프 끝 기호」에 대해서 개인적인 정리>
이전 판정 루프 : 종단에 종료 조건이 있기 때문에 한 번도 처리를 실행하지 않을 수 있음
후 판정 루프 : 시단에 종료 조건이 있기 때문에, 반드시 1회는 처리를 실행한다
따라서
전 판정에서는, 언제까지 반복하면 되는지 알고 있는 경우에 사용한다.
후 판정에서는, 언제까지 반복하면 되는지를 처리 ​​실행 후의 값으로 판단하는 경우에 사용한다.
상기 2문이 이 책에는 강조해 기재되어 있지 않았기 때문에, 무엇을 위해서 후판정이 존재하고 있는 것인가? 등 조금 생각해 버렸습니다.

또한 본문에는
예를 들면, 10만회 입력하는 경우, 전 판정이 10만회의 비교에 대해, 후판정은 20만회의 비교가 행해지므로, 그 차이는 분명하다
라는 설명이 있고, 처음? ? ? 되었습니다.

아래 그림을 살펴보겠습니다.
루프전에 1건째를 입력하는지, 루프후에 1건째를 입력하는가가 주된 차이.
루프 앞에서 첫 번째 항목을 입력하면 (2)의 사전 결정형 루프가되어 효율적입니다.

 (1)후 판정 루프           (2)전 판정 루프

플로우 차트는이 사이트에서 작성 → htps : // 어 p.ぢあgらms. 네 t/

반복 회수가 정해져 있는 경우는, 후판정에서는 각 루프 2회씩(마름모형 부분과 합계 금액의 1전의 부분) 비교해 버리므로, 처리가 2배가 되어, 비효율이라고 하게 됩니다 .

이마이치 이미지 쉬웠기 때문에, 이런 구체예를 생각했습니다.
도 경주로 A~Z까지 랜덤하게 1명씩 달려, G가 도착한 시점에서 경기 종료로 하고, 거기까지 달린 합계 주자수를 카운트합니다.
(1) 후 판정 루프에서는, 총 주자수를 산출할지(처리 실행)인지 판단하기 위해 스타트 지점에서 주자가 G인 것을 체크(마름모양 부분)하고, 경기 종료하기(루프에서 빠져나가기 위해) 골 지점에서 다시 러너가 G인지 확인하고 있습니다. 매 레이스마다 스타트 지점(1회째)과 골 지점(2회째)에서 G인지 체크가 이루어져 비효율적입니다. 자신이 심판이었을 경우, 합계 주자수 산출을 실시할지 어떨지와 시합을 종료할지 어떨지를 한꺼번에 하고 싶다! 라고 생각합니다.
(2)전 판정 루프에서는, 스타트 지점에서 러너가 G인지 체크하면, 그 녀석에 설레임을 걸어 골 지점에 알리는 것으로, 경기 종료의 판단을 하지 않아도 되도록 궁리하고 있습니다. 이것에 의해, 스타트 지점(1회째)에서의 체크만으로 좋아지므로 비교 횟수를 줄일 수 있다고 합니다.
이 예에서는, 전 판정이 추천됩니다만, 여기로부터 한층 더 각 러너는 1~9까지의 숫자 카드를 가지고 있어 그 합계가 30을 넘었을 경우에서도 루프를 빠질 수 있다고 하는 조건을 붙입니다 그렇다면, 이것은 몇 번 반복하면 그 조건을 채울지 불명하기 때문에 전 판정할 수 없네요. 이 경우, 후판정을 이용합니다.

좋은 웹페이지 즐겨찾기