알고리즘 학습 (5) 500 만 이내 의 친화 수 를 구하 고 연속 데이터 매 핑 은 배열 이다.
4379 단어 알고리즘
/*************************************************************************
> 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 로 메모 리 를 방출 할 수 있 습 니 다.동적 메모리 의 생존 기간 은 우리 가 결정 할 수 있다.
요약: 연속 데이터 의 매 핑 은 배열 구조 자체 의 특징 을 통 해 공간 을 절약 할 수 있다. 이것 은 데이터 구조의 예술 이다. 대규모 연속 데이터 의 역 추적 법 처리 에 있어 전달 생 성 방법 으로 전환 하고 역방향 사고 조작 으로 전환 하 는 것 이 알고리즘 의 기술 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.