c++문제풀이 도움주시면 감사드리겠습니답
조회수 1205회
백준 문제를 풀다가 막히는 부분이 있어서 질문드립니다 https://www.acmicpc.net/problem/12779(문제 원본) 분자가 주어진 범위안의 제곱수이고 분모가 주어진 범위인 문제입니다 여기까지는 정상적으로 돌아갔는데 조건중 '기약분수형태'로 표현하라는 구문이 있어서 분자와 분모를 각 최대공약수로 나누어주는 함수를 추가하였더니 엉뚱한 값이 출력되는데 어디가 문제인지 알려주시면 정말 감사드리겠습니다.
//
#include <iostream>
#include <cmath>
using namespace std;
unsigned int findpow(unsigned int m);
unsigned int gcd(unsigned int q, unsigned int p);
int main(){
unsigned int a, b;//0~(2의30승의제곱)
cin >> a >> b;
if (findpow(b) - findpow(a) == 0) { cout << '0'; }
else {
cout << (findpow(b) - findpow(a))/gcd(findpow(b), findpow(a)) << '/' << (b - a)/gcd(findpow(b), findpow(a));
}return 0;
}
unsigned int findpow(unsigned int m) {//제곱수구하기
for (int i = 1; i < pow(2, 30); i++) {
if (m < pow(i, 2)) {
break;
}return (i - 1);
}
}
unsigned int gcd(unsigned int q, unsigned int p) {
unsigned int k = 0;
while (p != 0){
k = q % p;
q = p;
p = k;
}
return p;
}
3 답변
-
unsigned int gcd(q, p)
가 수상합니다.while
무한루프로 최대공약수를 찾는 거라면 대충 이렇게 하시면 될텐데요? (제가 C를 몰라서 파이썬으로 알고리즘만 설명합니다.)def gcd(a, b) : # 공약수 후보를 선정한다. # 재수가 좋으면 둘중 더 작은 수로 더 큰 수가 나누어 떨어질 수 있으니 일단 그놈을 후보로 잡는다. c = a if a < b else b # 지금 공약수 후보를 가지고 두 수를 mod 연산해 본다. while a % c != 0 or b % c != 0 : # 둘 중 하나라도 나누어 떨어지지 않는다면 지금의 후보에서 1을 빼서 그걸로 다시 해 본다. c = c - 1 # 둘 다 나누어 떨어졌다면 지금 공약수 후보가 실제 최대공약수다. return c # 야! 너두 최대공약수 구할 수 있어! print(gcd(7, 3)) print(gcd(24, 18)) print(gcd(16*17, 12*17))
도움이 되었으면 좋겠네요.
-
엽토군님 코드를 c로 그대로 옮겨드립니다.
- gcd.cpp
unsigned int gcd(unsigned int a, unsigned int b) { int c = a < b ? a : b; while((a % c != 0) || (b % c != 0)) { c -= 1; } return c; }
나머지 이것저것 손봤습니다.
- cling(c++ 인터프리터입니다.)
[cling]$ .L main.cpp [cling]$ main() 1/3
- main.cpp
#include <iostream> #include <cmath> using namespace std; unsigned int findpow(unsigned int m); bool issquare(unsigned int n); unsigned int gcd(unsigned int a, unsigned int b); unsigned int findpow(unsigned int m) { for (int i = 1; i < pow(2, 30); i++) { if (m == pow(i, 2)) { return i; } } return 0; } // 제곱수 판별 bool issquare(unsigned int n) { return pow(pow(n, 0.5), 2) == n; } unsigned int gcd(unsigned int a, unsigned int b) { int c = a < b ? a : b; while((a % c != 0) || (b % c != 0)) { c -= 1; } return c; } int main() { int a = 1, b = 4; if(issquare(a) && issquare(b)) { cout << int((findpow(b) - findpow(a))/gcd(findpow(b), findpow(a))) << "/" << int((b - a)/gcd(findpow(b), findpow(a))) << endl; }else{ cout << '0' <<endl; } return 0; }
-
unsigned int findpow(unsigned int m) {//제곱수구하기 for (int i = 1; i < pow(2, 30); i++) { if (m < pow(i, 2)) { break; } } return (i - 1); }
그리고, 약분을 하려면, 분자와 분모의 공약수로 나눠야 하는데, 이상한 공약수를 구해서 나누고 있어요.
댓글 입력