블 루 브리지 컵 알고리즘 향상 - 특수 한 질수 늑골 자바 실현

2489 단어 알고리즘블 루 브리지 컵
특수 한 질수 늑골
농민 존 암 소 는 항상 가장 좋 은 늑골 을 만들어 낸다.너 는 농민 존 과 미국 농업 부 를 통 해 갈비뼈 에 표 시 된 숫자 를 통 해 그것들 을 알 아 볼 수 있다.농민 존 은 그 가 구매자 에 게 파 는 것 이 진정한 질수 늑골 이 라 고 확정 했다. 왜냐하면 오른쪽 부터 늑골 을 자 르 기 시 작 했 고 매번 남 은 늑골 의 숫자 는 하나의 질 수 를 구성 하기 때문이다.
예 를 들 어 네 개의 늑골 이 있 는 숫자 는 각각 7, 3, 1 이 고 모든 늑골 의 숫자 7331 은 질 수 이다.세 개의 늑골 733 은 질 수 이다.두 갈비뼈 73 은 질 수 이다.물론 마지막 갈비뼈 7 도 질 수 였 다.7331 은 길이 4 의 특수 한 질 수 라 고 불 린 다.
주어진 늑골 의 수 N (1 < = N < = 8) 을 작성 하여 모든 특수 질 수 를 구하 십시오.숫자 1 은 하나의 소수 로 간주 되 지 않 는 다.
입력 형식:
단독 줄 은 N 을 포함 합 니 다.
출력 형식:
줄 마다 길이 가 N 인 특수 질 수 를 순서대로 출력 합 니 다.
입력 예시:
4

출력 예시:
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

생각:
이 문 제 는 처음에는 폭력 적 으로 질 적 판단 을 하려 고 했 지만 마지막 두 테스트 점 은 데이터 가 너무 커서 시간 을 초과 했다.뒤에 참 고 했 어 요.https://blog.csdn.net/DyP__CSDN / article / details / 104178656 한 선배 의 블 로 그 는 재 귀 판단 이 n 위 에서 n 위 까지 더욱 간단 하 다 는 것 을 발견 했다. 예 를 들 어 7331, 7 을 먼저 판단 한 다음 에 73, 그리고 733, 마지막 7331 이다.재 귀 함 수 는 두 개의 매개 변수 로 들 어 갑 니 다. 하 나 는 소수 여 부 를 판단 하 는 x 이 고 하 나 는 문제 가 요구 하 는 수의 길이 length 입 니 다. 길이 가 n 과 같 고 소수 라 고 판단 하면 출력 입 니 다. n 보다 작 으 면 순환 판단 (x * 10 + i) 이 소수 인지 재 귀 하여 출력 을 판단 하면 됩 니 다.아래 에 코드 를 첨부 합 니 다:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.function.IntToDoubleFunction;

import javax.print.attribute.Size2DSyntax;
import javax.security.auth.x500.X500Principal;
import javax.swing.text.Highlighter;

import org.omg.PortableServer.ID_ASSIGNMENT_POLICY_ID;


public class Main{
	static int n;
	public static int fun(int x) {   //       
		int flag=0;
		if(x==1)
			flag=-1;
		for (int i = 2; i <= Math.sqrt(x); i++) {
			if(x%i==0)
			{
				flag=-1;
				break;
			}
		}
		return flag;
	}
	public static void dfs(int x,int length) {   //      
		if(length>n)   //       
		{
			System.out.println(x);
		}
		else {
			for (int i = 1; i <= 9; i++) {
				if(fun(x*10+i)==0)
				{
					dfs(x*10+i, length+1);
				}
			}
		}
	}
	public static void main(String args[]) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Scanner sc=new Scanner(System.in);
		
		n=Integer.parseInt(br.readLine());
		dfs(0, 1);
	}
}
변수 (Variable) - 2
[동적 계획] 돌 합병 문제 (링) (ssl 1597)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage