C언어 - 최대공약수 구하기

C언어 문제

사용자에게 정수 2개를 입력받아 최대공약수를 찾는 함수 gcd를 작성하시오.

*재귀호출과 반복문 두 가지 방법 모두 구현하기

1.main 함수

scanf함수를 통해 두 정수를 입력받는다.

두 정수를 findGCD함수에 인자로 넣어 remin에 최대공약수를 리턴값으로 받는다.

최대 공약수를 출력한다.

2.최대공약수 구하는 함수

①findGCD 함수 - 재귀호출 함수

함수의 타입을 int로 잡는다. return값을 최대공약수로 받기 위해서 이다.

인자는 main함수에서 입력받은 두 정수를 넣어준다.

최대공약수를 구하는 방법은 유클리드의 호제법을 사용한다.

유클리드의 호제법은 두 정수가 있을 때 큰 수를 작은 수로 나눈다. 나눈 나머지가 0이라면 두 정수의 최대공약수는 작은 수(작은 수)이다. 나머지가 0이 아니라면 원래 있던 큰 수는 버리고 작은 수와 나머지만 생각한다. 작은 수를 나머지로 나누고 나머지가 0이라면 최대공약수는 나머지가 된다. 그렇지 않다면 이 과정을 반복한다.

(참고 위키 백과 유클리드 호제법 - https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95)

재귀함수는 return 값이 자신 함수를 가진다. 호제법에서는 나머지에 따라 반복적인 행위를 계속해야하기 때문에 재귀함수를 사용할 수 있다.

인자로 받은 두 정수를 큰 수와 작은 수로 구분해 주고 큰 수를 작은 수로 나눈다. 이 때 나머지를 re라는 변수에 담는다. if - else문으로 re가 0이 아닐 때와 0일 때의 경우로 나눈다. 0이 아니라면 findGCD를 반복해야 하기 때문에 return 값은 findGCD(작은 수, 나머지)가 된다.

0일 경우는 나눈 수가 나머지이기 때문에 return 값은 작은 수가 된다.

<전체 코드>

②findGCD 함수 - 반복문 사용

유클리드 호제법은 위에서 사용했기 때문에 다른 방법을 사용해 보겠다.(하지만 숫자가 커지면 이 방법보다는 호제법이 훨씬 연산 정도가 적다.)

두 정수 중 큰 수와 작은 수를 정리한다. 그리고 작은 수와 같은 값을 가진 변수(i)를 이용해 입력 받은 두 수를 모두 변수(i)로 나눈다. 이때 나머지가 모두 0일 때 i는 최대공약수이며 모두 0이 아니라면 i를 1감소시킨다. 이 과정이 반복되어 i가 1이 되면 반복을 멈추고 i를 출력한다.

<전체코드>

**유클리드의 호제법을 반복문으로 구현하기

큰 수를 작은 수로 나눴을 때 나머지가 0일 경우에 반복문을 빠져나와 최소공배수를 return한다.

이 블로그의 인기 게시물

C언어 - 1~100 사이의 소수 구하기

C 문제 정수 값을 인자로 받아서 소수인지 판단하는 IsPrime 함수를 정의하고 이 함수를 이용해 1 부터 100 사이의 소수를 모두 구해서 출력하는 프로그램을 작성하시오 . 1.main 함수 만들기 IsPrime 이라는 함수에 인자를 2 부터 99 로 넣어주는 함수를 만들어야 한다 . 반복을 위해 for 함수를 사용한다 . main 함수의 타입이 int 이기 때문에 return 값을 적어줘야 함 . 2.IsPrime 함수 만들기 딱히 반환해야 할 값이 없기 때문에 타입은 void 경우를 2 가지로 나눔 . ①if 인자가 2 일 경우 --> 2 는 소수이기 때문에 2 를 출력함 ②else 인자가 2 가 아닐 경우 --> 2 부터 ( 인자 -1) 까지의 수로 인자를 나눠서 모든 경우에 나머지가 0 이 아니면 소수임 . 즉 어떤 숫자로 나눠 떨어지면 소수가 아니라는 의미로 더이상의 경우를 확인할 필요가 없음 . 따라서 반복하던 for 문을 빠져나옴 . for 문이 끝난 후 인자의 값과 count 의 값이 같다면 count 의 어떠한 숫자로도 인자가 나누어지지 못했다는 의미이다 . 이는 소수라는 뜻과 마찬가지이기 때문에 이 경우에 인자를 출력한다 . 3. 기타 출력한 후 모습을 살펴보는데 IsPrime 에서의 출력이 숫자 끝에 콤마 (,) 가 붙기 때문에 모든 출력이 끝나도 마지막 숫자 뒤에 콤마가 붙어 있다 . 이를 없애기 위해서는 이스케이프 문자 ‘\ b’ 를 사용했다 . 출력 화면이 더 편하게 보이도록 ‘\b\n’ 를 썼으나 이럴 경우 '\b' 의 효과가 사라졌다 . ‘\b\b\n’ 처럼 사용했으나 결과는 역시나 \ n 의 효과만 나타날 뿐 \ b 의 효과는 없었다 . 이를 해결하기 위해 구글링도 했지만 적절한 답을...

자세한 내용 보기

C언어 - 입력받은 숫자의 이진수 표현에서 1의 개수를 세는 코드를 짜기

C 언어 문제: 입력받은 숫자의 이진수 표현에서 1의 개수를 세는 코드를 짜기 이 문제를 해결하기 위해서는 시프트 연산자에 대해 알아야 한다. 컴퓨터에서는 숫자를 2진수로 표현하는데 정수는 32비트로 나타낸다. 가장 앞쪽에 있는 비트는 음수와 양수를 구분해 주는 비트이고 이 이하가 숫자를 의미한다. 시프트 연산자는 숫자를 이진수로 표현했을 때 연산을 편리하게 해 주는 연산자이다. 연산자에 대해 자세히 알고 싶으면 ( http://rockykim5581.tistory.com/19 )을 참고하길 바란다. 여기에서는 필요한 부분만 다룰 예정이다. 1. 숫자 입력받기 입력한 숫자를 변수에 대입해야 한다. 2.입력한 숫자의 이진수 표현에서 1의 개수 구하기 이진수에서도 비교 연산자를 사용할 수 있다. AND를 의미하는 &는 두 수가 모두 1일 때만 1(참)을 나타낸다. 이 성징을 이용하면 입력받은 숫자의 이진수를 셀 수 있다. 비트는 1부터 31가지 비교해야 한다.(32비트-사인비트-는 제외) 이 과정을 하기 위해서는 반복문이 필요하다. 여기서는 조건과 초기화, 반복후 실행하는 문이 있어서 for를 사용했다. 비교는 입력은 숫자(이진수 표현)의 n번째(이는 0아니면 1이다)와 n번째가 1인 숫자를 &으로 비교해서 둘 다 모두 1인 경우만 count라는 변수를 하나씩 올려준다. 그러면 입력받은 수의 이진수 표현 1을 셀 수 있게된다. 그러면 n번째가 1이라는 숫자를 어떻게 만들까? 이는 변수(one)를 하나 잡아 반복문의 실행에 따라 1을 시프트 연산자로 이동시킨 수를 대입한다. 예를 들어 처음일 때는 입력받은 수와 1을 옯기지 않은 상태로 비교, 두번째 자리를 비교할 땐 입력받은 수와 1을 한칸 옮긴 상태로 비교하는 식이다. 여기서 주의해야 할 점은 (비교하려는 자리의 수-1)만큼 시프트 연산자로 밀어줘야 한다는 것이다. 1이 한 자리도 차지하기 때문이다. <전체 코드> ...

자세한 내용 보기

C언어 - 입력된 정수 홀수와 짝수로 나눠 크기순으로 출력하기

2 번째 주 - C 언어 문제 길이가 10 인 배열을 만들고 그 배열에 10 개의 정수를 입력 받는다 . 이 때 입력받은 정수가 홀수면 배열의 앞부터 채워나가고 짝수면 배열의 맨 뒤에서부터 채워나가는 프로그램을 만들어라 .( 정수는 항상 10 개를 모두 입력한다고 가정한다 .) 실행화면 조건 1. int arr[10], i, num[10];// arr = 짝수 홀수 정리할 배열 , num = 숫자 입력 배열 \ 2.int lennum =() ; // 배열 num 의 크기 , 배열 입력받을 때 for 문에서 10 으로 하지말 고 lennum 사용해서 받을 것 int lenarr =(); // 배열 arr 의 크기 , {1,3,5,7,9,1,8,6,4,2} 형식을 위해 사용 -->hint: sizeof 사용 3.lenarr 출력 포맷을 위 사진과 동일하게 만들기 위해 사용한다 . 처음과 끝은 { 과 } 를 사용하고 마지막 숫자 뒤에는 콤마가 없어야 한다 . -->hint: if 문 사용 < 풀이 > 코드는 총 4 부분으로 나뉜다 . 입력 받기 , 홀수 정리 , 짝수 정리 , 출력 . 1. 입력받기 입력 받기 위해 for 문을 사용해서 반복한다 . 여기서 조건을 만족시키기 위해 lennum 을 구해야 한다 . siezof 크기를 알려주는 함수인데 단순히 sizeof(num) 을 한다면 10 이 나오지 않는다 . 40 이 나올 것이다 . 이는 배열이 가진 인덱스 X 타입형의 크기 값이 총 배열의 크기이기 때문이다 . 따라서 lennum 을 구하기 위해서는 다음과 같이 해야 한다 . lennum = sizeof (num) / sizeof ( int ); for 문 안에서는 scanf 를 사용해 입력한 숫자를 num 배열에 넣는다 . 입력받기 코드 2. 홀수 정리 ...

자세한 내용 보기

studyForMe

이 블로그 검색