알고리즘 학습 (10), 계단 뛰 어 넘 기 문제, 패 리 티 정렬

단계 문제:
문제 설명: 한 계단 은 모두 n 급 으로 한 번 도 1 급 을 뛰 거나 2 급 을 뛰 는 것 을 선택 할 수 있 습 니 다.모두 몇 가지 점프 법 이 있 는 지 를 구하 고 알고리즘 의 시간 복잡 도 를 분석한다.분석: 만약 에 1 단계 만 있 으 면 f (1) = 1, 2 단계 가 있 고 두 가지 점프 법 이 있 으 며 두 번 으로 나 누 어 뛰 거나 한 번 에 2 급 을 뛴다.n 단계 계단 까지 확대, (n > 2) 첫 번 째 점프 할 때 또 두 가지 선택 이 있 습 니 다. 만약 에 첫 번 째 점프 라면 점프 법 수 는 f (n - 1) 와 같 고 다른 하 나 는 첫 번 째 점프 2 단계 입 니 다. 이때 점프 법 수 조 는 f (n - 2) 와 같 기 때문에 전체적인 점프 법 f (n) = f (n - 1) + f (n - 2) 는 fibonacci 수열 문제 와 유사 하여 재 귀 하 는 사상 을 사용 합 니 다.
패 리 티 순서
제목 설명: 정수 배열 을 입력 하고 배열 의 숫자 순 서 를 조정 하여 모든 홀수 가 배열 의 전반 부 에 있 고 모든 짝수 가 후반 부 에 있 습 니 다.분석: 한 배열 에서 앞 뒤 부분 과 관련 된 토론 은 앞 뒤 두 개의 지침 을 사용 할 수 있 습 니 다. 만약 에 첫 번 째 지침 이 짝수 를 가리 키 면 꼬리 지침 은 하나의 홀수 를 가리 키 고 두 개의 위 치 를 서로 바 꾸 어 두 지침 이 만 날 때 까지 합 니 다.이렇게 배열 의 숫자 는 홀수 가 모두 앞부분 에 있 고 짝수 는 후반 부분 에 있다.

#include <iostream>
using namespace std;

bool inEven(int n)  //       
{
    return (n&1)== 0;
}

void Reorder(int * data ,int length)
{
    int *begin = data;
    int * end = begin+length-1;
    while(begin < end)
    {
        if(!inEven(*begin))
        {
            begin++;
            continue;
        }
        if(inEven(*end))
        {
            end--;
            continue;
        }
        int temp;
        temp= *begin;
        *begin = *end;
        *end = temp;
    }

}
int main()
{
    int a[5] = {2,5,6,7,9};
    Reorder(a,5);
    int i;
    for(i = 0 ;i<5;i++)
        cout << a[i] << endl;
    return 0;
}

우 리 는 또한 이런 방법 을 양음 수 중 정렬 문제 에 응용 하여 음 수 를 전반 부 에 있 게 하고 정 수 는 후반 부 에 있 게 할 수 있다.
첫 번 째 문자
제목 설명: 한 문자열 에서 "abc be" 와 같은 첫 번 째 문자 만 찾 으 면 "a" 를 출력 합 니 다.분석: 배열 에 수반 되 는 방법 을 사용 하여 문 자 를 아래 표 로 하고 나타 나 는 횟수 를 대응 하 는 값 으로 하 며 첫 번 째 값 이 1 이 고 대응 하 는 문 자 를 찾 을 수 있 습 니 다.

#include <iostream>
using namespace std;
const int SIZE = 100;
char odd_even_swap(char * str)
{
    char * p;
    int index ;
    int data[SIZE] = {0};
    if(str == NULL)
        return '\0';
    p = str;
    while( *p != '\0')
    {
        index = *p++-'a';
        data[index]++;
    }
    int i;
    char result;
    for(i = 0;i<SIZE;i++)
    {
        if(data[i] ==1)
            return i+'a';

    }
}
int main()
{
    char str[10] = "abcade";
    cout << odd_even_swap(str) << endl;
    return 0;
}

물론, 우 리 는 문 자 를 배열 로 표시 할 수도 있 지만, 배열 의 크기 에 주의 하여 경 계 를 넘 지 않도록 해 야 한다.

char odd_even_swap2(char * str)
{
    char *p;
    const int size = 200;   //'a' ascii  97,        。
    int tablesize[size] = {0};
    p = str;
    while(*p != '\0')
    {
        tablesize[*(p++)]++;
    }
    while(*str++ != '\0')
    {
        if(tablesize[*str] == 1)
            return *str;
    }
    return '\0';
}