알고리즘 학습 (5) 500 만 이내 의 친화 수 를 구하 고 연속 데이터 매 핑 은 배열 이다.

제목 설명: 500 만 이내 의 모든 친화 수 를 구하 고 만약 에 두 개의 수 a 와 b, a 의 모든 진인 수의 합 이 b, b 의 모든 진인 수의 합 이 a 와 같다 면 a, b 는 한 쌍 의 친화 수 라 고 부른다.진인 수: 그 자 체 를 제외 한 모든 인수, 예 를 들 어 220 의 진인 수: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110;284 의 진인 수: 1, 2, 4, 71, 142. 220 = 1 + 2 + 4 + 71 + 142 = sum [284] 284 = 1 + 2 + 4 + 5 + 10 + 11 + 22 + 44 + 55 + 110 = sum [220] 분석: 한 수의 인수 가 그것 의 절반 을 넘 지 않 으 면 우 리 는 수 조 를 이용 하여 수 를 배열 로 표시 할 수 있 고 배열 의 대응 요 소 는 진인 수의 합 이 며 그 후에 sum [sum] = i 의 i 를 만족 시 키 고 sum [i] 와 한 쌍 의 친화 수 를 누 릴 수 있다.우선 초기 화 할 때 배열 은 항목 마다 1 이 있 습 니 다. 1 은 모든 수의 진짜 인수 이기 때 문 입 니 다.그 다음 에 인수 i 는 2 부터 n / 2 까지 그 자체 가 진짜 인수 가 아니 기 때문에 대응 항목 은 2i 부터 3i, 4i, 5i... k * i > n 까지 모두 인수 i 를 포함한다.이 모든 항목 의 sum [2i], sum [3i].그리고 친화 적 인 조건 을 충족 시 키 는 항목 을 찾 아 헤 매 기 시작 할 수 있다.i = 2 시, sum [4] + = 2, sum [6] + = 2;sum [8] + = 2... i = 3 시, sum [6] + = 3;sum[9]+= 3;sum [12] + = 3... i = 4 시, sum [8] + = 4;sum[12] +=4…

/*************************************************************************
 > File Name: find_qinhe.c
 > Author: zxl
  > mail: [email protected]
 > Created Time: 2016 04 18      20 36 58 
 ************************************************************************/

#include<stdio.h>
#define SIZE 5000000
int main()
{
 static int sum[5000001]; //        ，       
 int i,j;
 for(i = 1;i<= SIZE;i++)
 sum[i] = 1; //      1
 for(i = 2;i+i<=SIZE;i++) //      ，
 {
 j = 2*i;
 while(j<=SIZE) //    2，  n/2 ，    3，  n/3 ，     n(1/2 + 1/3+ 1/4 + 1/n/2)，        O（N* log N + N）
 {
 sum[j] +=i; //           
 j+=i;
 }
 }
 for(i = 220;i<=SIZE;i++)
 {
 if(sum[i]>i && sum[i] <=SIZE&& sum[sum[i]] == i)//  sum[i] >i       ，  sum[248] = 220
 {
 printf("%d,%d
",i,sum[i]);
 }
 }
 return 0;
}

주의해 야 할 때 큰 배열 이 정의 하 는 곳 은 함수 안에 있 으 면 분배 공간 이 모두 스 택 에 있 고 스 택 은 비교적 유한 하 며 큰 공간 은 모두 정적 저장 구역 에 분배 되 어 전체 또는 함수 에 static 를 정의 할 수 있 습 니 다.다른 것 도 참고 하여 프로 그래 밍 가능 한 메모 리 는 정적 저장 소, 쌓 기 영역 과 스 택 영역 정적 저장 소 로 나 눌 수 있 습 니 다. 메모 리 는 프로그램 이 컴 파일 할 때 이미 분배 되 었 습 니 다. 이 안에 프로그램의 전체 운행 기간 이 존재 합 니 다. 주로 정적 데이터, 전체 데이터 와 상수 가 저 장 됩 니 다.스 택 구역: 함 수 를 실행 할 때 함수 내 부분 변수의 저장 부 는 스 택 에서 만 들 수 있 습 니 다. 함수 실행 이 끝 날 때 이 저장 부 는 자동 으로 방출 됩 니 다.스 택 메모리 할당 연산 은 프로세서 의 명령 이 집중 되 고 효율 이 높 지만 분 배 된 메모리 용량 은 제한 되 어 있 습 니 다.쌓 기 영역: 동적 메모리 할당 이 라 고 합 니 다. 프로그램 이 실 행 될 때 malloc 나 new 로 임의의 크기 의 메모 리 를 신청 하면 적당 한 시간 에 free 또는 delete 로 메모 리 를 방출 할 수 있 습 니 다.동적 메모리 의 생존 기간 은 우리 가 결정 할 수 있다.
요약: 연속 데이터 의 매 핑 은 배열 구조 자체 의 특징 을 통 해 공간 을 절약 할 수 있다. 이것 은 데이터 구조의 예술 이다. 대규모 연속 데이터 의 역 추적 법 처리 에 있어 전달 생 성 방법 으로 전환 하고 역방향 사고 조작 으로 전환 하 는 것 이 알고리즘 의 기술 이다.