분 치 법 예
2818 단어 알고리즘
알고리즘 설명: 문 제 를 하위 문제 로 나 누 어 하나 또는 두 개의 요 소 를 비교 할 때 가장 큰 값 은 그 자체 이 고 두 개의 요소 일 때 가장 큰 값 은 비교적 큰 것 이 고 큰 값 은 작은 것 입 니 다.최소 상황 이 아니라면, 문 제 를 작은 문제 로 나 누 어 라.마지막 으로 앞의 최대 치 차 대 치 와 뒤의 최대 치 차 대 치 를 되 돌려 주 고 이 네 개의 수 를 비교 합 니 다. 만약 에 뒤의 최대 치가 최대 치 보다 크 면 최대 치 는 max 1 이 고 다시 큰 값 을 비교 하면 큰 값 은 큰 값 을 줍 니 다.이 문 제 는 두 번 의 최대 치 와 차 대 치 를 어떻게 비교 하 느 냐 가 관건 이다.원본 프로그램:
#include
using namespace std;
int a[100];
/* */
void Max12(int i,int j,int &max,int &mimax){
int max1,mimax1;
if(i==j){// ，
max=mimax=a[i];
}
else if(i==j-1){// ， ，
if(a[i]max) {/ / 뒤에 최대 치가 최대 치보다 크 면 최대 치 를 변경 합 니 다.
mimax=max;
max=max1;
if(mimax1>mimax)
mimax=mimax1;
}
else if (max 1 > mimax) {/ / 뒤의 최대 치 는 차 보다 크 고 차 대 치 를 변경 합 니 다.
mimax=max1;
}
}
}
int main(){
int n,i;
int max,mimax;
cin>>n;
for(i=0;i>a[i];
max = a [0]; / / 최대 치 큰 값 으로 초기 화
mimax=a[0];
Max12(0,n-1,max,mimax);
cout< 빠 른 정렬
알고리즘 설명: 주어진 서열 을 큰 것 에서 작은 것 으로 정렬 하고 빠 른 정렬 을 쓰기 전에 구분 함 수 를 써 야 합 니 다.구분 함 수 는 첫 번 째 값 보다 큰 것 을 왼쪽 에 놓 고 작은 것 을 오른쪽 에 놓 을 수 있다.여기 감시 초 소 를 설치 하여 시퀀스 의 끝 값 을 무한소 로 부여 하여 i 경 계 를 넘 지 않도록 합 니 다.i. 첫 번 째 값 보다 작은 정 지 를 찾 을 때 까지 j 는 첫 번 째 값 보다 큰 정 지 를 찾 을 때 까지 앞으로 갑 니 다. 만약 에 i, j 가 교차 하지 않 으 면 두 요 소 를 교환 합 니 다. i, j 가 교차 할 때 까지.마지막 으로 j 의 값 과 첫 번 째 값 을 교환 하고 첫 번 째 값 은 순 서 를 정 했다.
원본 프로그램:
#include
using namespace std;
int a[100];
/* */
int Pa(int left,int right){
int i=left;
int j=right+1;
int temp=a[j];// right ,
a[j]=0x80000000;
do{
do
i++;
while(a[i]>a[left]);//i
do
j--;
while(a[j]>n;
for(i=0;i>a[i];
}
a [n] = 0x 80000000; / / 마지막 은 무한대 로 감시초 소 로
QuickSort(0,n-1);
for(i=0;i k 번 째 요소 찾기
알고리즘 설명: k 작은 요 소 를 찾 고 patition 구분 함 수 를 이용 하여 한 번 도 찾 지 않 으 면 j + 1 작은 것 을 찾 을 수 있 습 니 다. 이 점 을 이용 하여 K 작은 것 을 찾 을 때 까지 구분 함 수 를 계속 호출 합 니 다. 여기 서 주의해 야 할 것 은 j 와 k 크기 를 비교 하여 호출 순 서 를 줄 이 는 것 입 니 다. 예 를 들 어 절반 으로 찾 을 때 j 왼쪽, 시간, 오른쪽 을 찾 습 니 다.
원본 프로그램:
#include
using namespace std;
int a[100];
/* */
int Pa(int left,int right){
int i=left;
int j=right+1;
int temp=a[j];
a[j]=0x7fffffff;
do{
do
i++;
while(a[i]a[left]);
if (ik) / / j 가 크 면 K 가 작 으 면 왼쪽 에 있 을 거 예요.
j=Pa(left,j-1);
else if(j>n;
for(i=0;i>a[i];
}
cin>>x;
j = find (0, n - 1, x - 1); / x - 1 은 배열 아래 표 시 를 적응 하기 위해 서 입 니 다.
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
