알고리즘 문제 1

제목 1: 두 바 이 너 리 수의 차이 나 결과
두 개의 이 진수 가 다 르 거나 결 과 는 이 두 개의 이 진수 차 의 절대 값 입 니 다. 즉, 다음 과 같이 표 현 됩 니 다. a ^ b = | a - b | (비트 별로 감소) 해답 과정:      이 진수 a 와 b 가 다 르 거나, 즉 a 와 b 두 수 는 위치 에 따라 진행 되 며, 대응 위치 가 같 으 면 0 (이때 대응 위치 산술 의 상쇄 에 해당 함) 이 고, 다 르 면 1 (이때 대응 위치 산술 의 상쇄 에 해당 하 는 절대 치) 이다.이 진 은 각 비트 에 두 가지 상태 만 있 기 때문에 0 이 든 1 이 든 위치 에 따라 이동 하거나 조작 하면 위치 에 따라 감 소 된 후에 절대 치 를 취 하 는 것 으로 나 타 낼 수 있다.문제 2: 재 귀 함수 가 최종 적 으로 끝 날 것 입 니 다. 그러면 이 함 수 는 반드시 (항목 선택 하지 않 음): 1. 부분 변 수 를 사 용 했 습 니 다. 2. 한 가지 가 자신 을 호출 하지 않 습 니 다. 3. 전역 변 수 를 사 용 했 거나 하나 이상 의 인 자 를 사 용 했 습 니 다. 이것 은 간단 한 선택 문제 이지 만 포 함 된 내용 은 간단 하지 않 습 니 다. 항목 선택 이 더욱 어렵 습 니 다.나 는 한눈 에 보 니 자 연 스 럽 게 2 와 3 을 선택 했다.1. 분명 한 것 은 아니다. 국부 변 수 는 한 번 에 국부 범위 에서 만 유효 하고 이번 호출 범위 가 나 오 면 무효 이 며 재 귀적 인 끝 을 통제 할 수 없다.(이 옵션 은 국부 변수의 생명주기 / 유효 범 위 를 검사 하 는 문제) 주의해 야 할 것 은 국부 변수 가 국부 정적 변수 가 아니 라 는 것 이다.2. 자 연 스 럽 습 니 다. 자신 을 호출 하지 않 는 분기 가 없 으 면 재 귀 는 끝나 지 않 습 니 다.(이것 은 재 귀적 정 의 를 검사 하 는 것 입 니 다) 3 에 대해 가장 현혹 적 입 니 다. 전역 변 수 를 사용 하거나 하나 이상 의 매개 변 수 를 사용 하면 재 귀적 인 끝 을 제어 할 수 있 지만 이 두 가지 방식 만 있 는 것 이 아 닙 니까?그래서 제목 에서 '꼭' 을 지적 했다.답 은 이 두 가지 방식 만 있 는 것 이 아니다.    * 우 리 는 스 택 이 아 닌 부분 정적 변 수 를 쌓 아 두 는 것 을 알 고 있 기 때문에 프로그램 수명 주기 에 모두 존재 합 니 다. 함수 에서 만 접근 할 수 있 습 니 다. 그 내용 은 지난번 에 처 리 된 내용 이나 초기 화 된 내용 으로 여러 번 같은 변 수 를 호출 합 니 다.그래서 국부 정적 변 수 는 귀속 함 수 를 제어 하여 최종 적 으로 끝 낼 수 있다.      C 언어 에서 사용 할 수 있 습 니 다.      static int a;      Delphi 에서 사용 할 수 있 습 니 다.      const a:integer;      정의 (컴 파 일 러 스위치 $J + 주의)      여기 서 많은 사람들 이 국부 정적 변 수 는 전역 변수 라 고 생각 할 것 이다. 이것 은 잘못된 것 이다. 전역 변 수 는 생명주기 와 유효 작용 역 이 모두 전역 성 을 가 져 야 한다. 반면에 국 총 정적 변 수 는 생명주기 만 전역 이 고 작용 역 은 함수 체 내 에서 만 유효 하 다.    * 이상 을 통 해 귀환 의 끝 을 제어 할 수 있 습 니 다.사실 이런 상황 은 흔히 볼 수 있 습 니 다. 모든 프로그램의 부족 한 스 택 공간 크기 는 그리 크 지 않 고 스 택 이 넘 쳐 서 재 귀 함수 가 종료 되 기 쉽 습 니 다.그 밖 에 메모리 공간 부족, 제로 제거 등 다른 이상 도 발생 할 수 있다.이 이상 들 은 재 귀 함 수 를 중지 시 킬 수 있다.    * 우리 가 일반적으로 말 하 는 전역 변 수 는 하나의 응용 프로그램 에 대한 것 이기 때문에 우 리 는 BIOS 나 OS 의 일부 데이터 나 표준 라 이브 러 리 의 전역 값 을 이용 하여 귀속 과정의 종 료 를 제어 할 수 있다.예 를 들 어 날짜 시간, 라 이브 러 리 의 임 의 수 를 이용 하 는 등 이다.    * 우 리 는 또한 일부 데 이 터 를 BIOS 나 OS 의 시스템 데이터 구역 에 기록 할 수도 있 고, 데 이 터 를 한 파일 에 기록 하여 재 귀 함수 의 종 료 를 제어 할 수도 있다.    * 그리고.......................................................................이상 의 종료 조건 은 앞의 두 가지 만 생각 하고 뒤의 것 은 다른 사람의 '창의' 를 종합 한 것 이다. D
제목 3: T (n) = 25T (n / 5) + n ^ 2 의 시간 복잡 도?T(n) = 25T(n/5)+n^2 = 25(25T(n/25)+n^2/25)+n^2= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n= 625(25T(n/125)+n^2/625) + 2n^2= 625*25*T(n/125) + 3n^2= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n= ....= 25 ^ x * T( n / 5^x ) + x * n^2T(n) = 25T(n/5)+n^2T(0) = 25T(0) + n^2 ==> T(0) = 0T(1) = 25T(0)+n^2 ==> T(1) = 1x = lg 5 n25 ^ x * T( n / 5^x ) + x * n^2= n^2 * 1 + lg 5 n * n^2= n^2*(lgn)
제목 4: 두 개의 N * N 행렬 의 곱셈 을 실현 하고 행렬 은 1 차원 배열 로 표시 한다.
void matrix_mul(int a[][], int b[][], int c[][])
{
　　for(int j=0;j　　{
　　　　int sum=0;
　　　　for(int i=0;i　　　　{
　　　　　　for(int k=0;k　　　　　　　　c[j][i]+=a[j][k]+b[k][i];
　　　　}
　　}
}
제목 5: 단 방향 링크 중간 에 있 는 요 소 를 찾 아 두 개 있 으 면 앞 에 있 는 요 소 를 가 져 옵 니 다.
두 개의 바늘 로 한 걸음 의 길 이 는 1 이 고 다른 걸음 의 길 이 는 2 이다. 걸음 길이 가 2 인 바늘 이 링크 의 꼬리 부분 에 갔 을 때 걸음 길이 가 1 인 지침 의 방향 은 바로 중간 에 있 는 요소 이다.
문제 6: 길이 가 n 인 정수 배열 은 그 중에서 임 의 (n - 1) 개 곱 하기 가 가장 큰 그룹 을 찾 아 곱셈 만 사용 할 수 있 고 나눗셈 을 사용 할 수 없다.알고리즘 의 시간 복잡 도와 공간 복잡 도 를 분석 해 야 하 며 프로그램 작성 을 요구 하지 않 습 니 다.
이 N 개의 곱셈 을 P 로,    1) P < 0 이면 그 중에서 가장 큰 마이너스 정 수 를 제거 하면 된다.    2) P = 0 이면,        2.1) 만약 에 이 N 개의 숫자 중 하나 가 '0' 이 라면.다른 수의 축적 이 플러스 라면 '0' 을 제거 합 니 다.그렇지 않 으 면 최대 마이너스 정 수 를 제거 합 니 다.        2.2) 만약 에 이 N 개 수 중 적어도 두 개가 '0' 이면 한 개 수 를 마음대로 삭제 해도 된다.    3) P > 0 이면 정수 가 있 으 면 그 중에서 가장 작은 정 수 를 제거 하면 된다.그렇지 않 으 면 가장 작은 음 정 수 를 제거한다.    시간 복잡 도: 배열 을 옮 겨 다 니 며 정수 cp, 마이너스 정수 cn, 0 의 개수 cz 를 얻 으 려 면 O (N) 시간 이 필요 합 니 다.제 거 된 수 를 찾 는 데 최 악의 경우 O (N) 시간 이 필요 합 니 다.출력 결 과 는 O (N) 시간 이 필요 합 니 다.따라서 시간 복잡 도 는 O (N) 다.    공간 복잡 도: 배열 저장 은 O (N) 공간, cp, cn, cz 와 제 거 된 수의 아래 표 시 는 각각 O (1) 공간 이 필요 합 니 다.따라서 공간 복잡 도 는 O (N) 이다.