-
Notifications
You must be signed in to change notification settings - Fork 5
algorithm primary arithmetic
Jongbin Oh edited this page Jun 8, 2013
·
1 revision
- 숫자를 입력받아 한자리씩 더하면서 올림이 발생하는지를 알아야 하는데, 한자리씩 접근하는것은 숫자보다 문자열 형태가 편할꺼라는 생각에 그렇게 코딩해서 제출했습니다.
- 그리고.. 작년에 제출했던 코드를 열어보니 올림이 발생할때 자리수의 규칙을 나름대로 정리해서 만들었던듯 하네요
- 작년 코드를 보니 숫자로 입력받아 한자리씩 더하면서 풀어도 됐을법 하더군요. 왜 문자열로 했지
#include <stdio.h>
#include <string.h>
int main()
{
char a[11], b[11];
int len_a, len_b, carry, result;
while( scanf("%s %s", a, b) )
{
if( a[0] == '0' && b[0] == '0' )
{
break;
}
len_a = strlen(a)-1;
len_b = strlen(b)-1;
result = 0;
carry = 0;
while( len_a >= 0 && len_b >= 0 )
{
if( a[len_a]-'0' + b[len_b] - '0' + carry >= 10 )
{
result++;
carry = 1;
}
else
{
carry = 0;
}
len_a--;
len_b--;
}
while( len_a >= 0 )
{
if( a[len_a]-'0' + carry >= 10 )
{
result++;
carry = 1;
}
else
{
carry = 0;
}
len_a--;
}
while( len_b >= 0 )
{
if( b[len_b] - '0' + carry >= 10 )
{
result++;
carry = 1;
}
else
{
carry = 0;
}
len_b--;
}
if(result)
{
printf("%d", result);
if( result == 1) printf(" carry operation.\n");
else printf(" carry operations.\n");
}
else
{
printf("No carry operation.\n", result);
}
}
return 0;
}
#include <stdio.h>
int main()
{
int a, b;
int add, result;
while(1)
{
scanf("%d %d", &a, &b);
if( !a && !b) break;
result = 0;
add = a + b;
while(add)
{
if( add%10 < a%10 || add%10 < b%10 ) result++;
if( add%10 == a%10 && add%10 == b%10 && a%10 == 9) result ++;
a /= 10;
b /= 10;
add /= 10;
}
if(result)
if( result == 1)
printf("%d carry operation.\n", result);
else
printf("%d carry operations.\n", result);
else
printf("No carry operation.\n");
}
return 0;
}
-
풀이
- 입력된 숫자들 뒷자리부터 각자리수별로 더하여 Carry가 있는지 검사한다.
- 10자리 숫자는 int형의 범위를 넘기때문에 문자열로 읽어들여 각자리를 처리 하였다
-
소스
import java.io.IOException; class Main implements Runnable{ static String ReadLn(int maxLength){ // utility function to read from stdin, // Provided by Programming-challenges, edit for style only byte line[] = new byte [maxLength]; int length = 0; int input = -1; try{ while (length < maxLength){//Read untill maxlength input = System.in.read(); if ((input < 0) || (input == '\n')) break; //or untill end of line ninput line [length++] += input; } if ((input < 0) && (length == 0)) return null; // eof return new String(line, 0, length); }catch (IOException e){ return null; } } public static void main(String args[]) // entry point from OS { Main myWork = new Main(); // Construct the bootloader myWork.run(); // execute } public void run() { String line = null; Adder adder = new Adder(); while((line = ReadLn(22).trim()) != null){ if(line.equals("0 0")){ break; } String [] nums = line.split(" "); if(nums.length != 2){ break; } int carryCount = adder.getCarryCount(nums[0], nums[1]); if(carryCount == 0){ System.out.println("No carry operation."); } else if(carryCount==1){ System.out.println(carryCount+" carry operation."); }else{ System.out.println(carryCount+" carry operations."); } } } } class Adder { public boolean isMakeCarry(int i, int j,boolean hasCarry) { int carray = hasCarry?1:0; return i+j+carray>=10; } public int getCarryCount(String adder, String addend) { int maxLen = Math.max(adder.length(), addend.length()); boolean hasCarry = false; int carryCount = 0; for(int index=0;index<maxLen;index++){ int a = getValueByPos(adder, index); int b = getValueByPos(addend, index); hasCarry = isMakeCarry(a, b, hasCarry); if(hasCarry){ carryCount++; } } return carryCount; } public int getValueByPos(String value,int pos){ if(value.length() <= pos) return 0; int cutPos = value.length()-pos-1; return Integer.parseInt( value.substring( cutPos,cutPos+1) ); } } -
TestCase
import junit.framework.TestCase; public class AdderTest extends TestCase { public void testIsMakeCarry(){ Adder adder = new Adder(); assertTrue(adder.isMakeCarry(5,5,false)); assertTrue(adder.isMakeCarry(5,4,true)); assertTrue(adder.isMakeCarry(5,6,false)); assertFalse(adder.isMakeCarry(5,3,false)); } public void testValuePos(){ Adder adder = new Adder(); assertEquals(1, adder.getValueByPos("1234", 3)); assertEquals(4, adder.getValueByPos("1234", 0)); } public void testGetCarryCount(){ Adder adder = new Adder(); assertEquals(0, adder.getCarryCount("123","456")); assertEquals(3, adder.getCarryCount("555","555")); assertEquals(2, adder.getCarryCount("55","555")); assertEquals(1, adder.getCarryCount("123" ,"594")); assertEquals(0, adder.getCarryCount("0","0")); } }
- 입출력 처리하지 않음
- 다른 분들 코드에 비해 오버플로우에 취약
- 몇자리 숫자까지 될라나?
' $Id: PrimaryArithmetic.vb 100 2008-02-25 06:33:34Z 정희종 $
Public Class PrimaryArithmetic
Function GetCarryCount(ByVal addend As Integer, ByVal augend As Integer) As Integer
Dim addends() As Integer = GetDigits(addend)
Dim augends() As Integer = GetDigits(augend)
' 길이 맞추기
If addends.Length > augends.Length Then
PadDigits(augends, addends.Length)
Else
PadDigits(addends, augends.Length)
End If
' 각 자리 숫자 더하여 carry 갯수 구하기
Dim carryCount As Integer
Dim carry As Integer
For i As Integer = 0 To addends.Length - 1
Dim digitSum = addends(i) + augends(i) + carry
If digitSum >= 10 Then
carryCount += 1
carry = 1
Else
carry = 0
End If
Next
Return carryCount
End Function
Function GetDigits(ByVal number As Integer) As Integer()
Dim digits As List(Of Integer) = New List(Of Integer)
While number > 0
digits.Add(number Mod 10)
number = Math.Floor(number / 10)
End While
Return digits.ToArray()
End Function
Sub PadDigits(ByRef digits() As Integer, ByVal length As Integer)
If digits.Length < length Then
ReDim Preserve digits(length - 1)
End If
End Sub
End Class
' $Id: PrimaryArithmeticTest.vb 100 2008-02-25 06:33:34Z 정희종 $
<TestClass()> _
Public Class PrimaryArithmeticTest
Private pr As PrimaryArithmetic = New PrimaryArithmetic
<TestMethod()> _
Public Sub GetDigitsTest()
Dim expected() As Integer = {3, 2, 1}
Dim actual() As Integer = pr.GetDigits(123)
Assert.AreEqual(expected.Length, actual.Length)
For i As Integer = 0 To expected.Length - 1
Assert.AreEqual(expected(i), actual(i))
Next
End Sub
<TestMethod()> _
Public Sub GetDigitsTestMore()
Dim expected() As Integer = {9, 9, 9}
Dim actual() As Integer = pr.GetDigits(999)
Assert.AreEqual(expected.Length, actual.Length)
For i As Integer = 0 To expected.Length - 1
Assert.AreEqual(expected(i), actual(i))
Next
End Sub
<TestMethod()> _
Public Sub PadDigitsTest()
Dim actual() As Integer = {3, 2, 1}
pr.PadDigits(actual, 5)
Dim expected() As Integer = {3, 2, 1, 0, 0}
Assert.AreEqual(expected.Length, actual.Length)
For i As Integer = 0 To expected.Length - 1
Assert.AreEqual(expected(i), actual(i))
Next
End Sub
<TestMethod()> _
Public Sub GetCarryCountTestNoCarry()
Assert.AreEqual(0, pr.GetCarryCount(22, 33))
End Sub
<TestMethod()> _
Public Sub GetCarryCountTest()
Assert.AreEqual(0, pr.GetCarryCount(123, 456))
Assert.AreEqual(3, pr.GetCarryCount(555, 555))
Assert.AreEqual(1, pr.GetCarryCount(123, 594))
End Sub
<TestMethod()> _
Public Sub GetCarryCountTestMore()
Assert.AreEqual(1, pr.GetCarryCount(4821, 311))
Assert.AreEqual(3, pr.GetCarryCount(999, 1))
Assert.AreEqual(4, pr.GetCarryCount(99099, 1001))
End Sub
End Class
-
한자리씩 더하면서 carry 을 체크하였습니다. 왠지 너무 어렵게 푼듯한 느낌이 --;
-
안 되잖아요~ 버럭 - CynicJJ
-
잇힝
public class PrimaryMain { int[] firNum = new int[10]; int[] secNum = new int[10]; public boolean parseInput(String fir, String sec) { if(fir.length() > 10 || sec.length() > 10) return false; char[] temp = fir.toCharArray(); for(int i=temp.length-1, j=0 ; i>=0 ; i-- , j++) { firNum[i] = Integer.parseInt(String.valueOf(temp[j])); } char[] temp2= sec.toCharArray(); for(int i=temp2.length-1, j=0 ; i>=0 ; i-- , j++) { secNum[i] = Integer.parseInt(String.valueOf(temp2[j])); } return true; } public int addOneDigit(int fir, int sec, int carry) { if( fir + sec + carry > 9) return 1; else return 0; } public void initNumbers(String in) { String[] input = in.split(" "); if(input.length > 2) return; parseInput(input[0],input[1]); } public int sumCarryCount() { int sumCarry = 0; int carry = 0; for(int i=0; i < firNum.length ; i++) { carry = addOneDigit(firNum[i],secNum[i],carry); if( carry == 1) sumCarry++; if( firNum[i] == 0 && secNum[i] == 0) break; } return sumCarry; } } import static org.junit.Assert.*; import java.util.Arrays; import org.junit.Test; public class PrimaryMainTest { PrimaryMain pri = new PrimaryMain(); @Test public void testSumCarryCount() { pri.initNumbers("123 456"); assertEquals(0,pri.sumCarryCount()); pri.initNumbers("555 555"); assertEquals(3,pri.sumCarryCount()); pri.initNumbers("123 594"); assertEquals(1,pri.sumCarryCount()); pri.initNumbers("146 554"); assertEquals(2,pri.sumCarryCount()); } @Test public void testParseInput() { pri.parseInput("15","4"); assertTrue(Arrays.equals(pri.firNum,new int[] {5,1,0,0,0,0,0,0,0,0})); assertTrue(Arrays.equals(pri.secNum,new int[] {4,0,0,0,0,0,0,0,0,0})); pri.parseInput("123","456"); assertTrue(Arrays.equals(pri.firNum,new int[] {3,2,1,0,0,0,0,0,0,0})); assertTrue(Arrays.equals(pri.secNum,new int[] {6,5,4,0,0,0,0,0,0,0})); } @Test public void testAddOneDigit() { assertEquals(0,pri.addOneDigit(4,5,0)); assertEquals(1,pri.addOneDigit(5,5,0)); assertEquals(1,pri.addOneDigit(4,5,1)); assertEquals(0,pri.addOneDigit(1,2,1)); } }
- Wrong Answer
-
복수개의 carry가 발생하면 operations. 라고 출력해야 합니다....;;;
#include <iostream> #include <vector> #ifdef _UNITTEST #include "../UnitTest++/src/UnitTest++.h" #include "../UnitTest++/src/TestReporterStdout.h" #endif //_UNITTEST using namespace std; int GetPrimaryArithmetic(int n1, int n2) { int iRet = 0; int each_digit_min = 0; int each_digit_max = 0; int carry = 0; int min_n = min(n1, n2); int max_n = max(n1, n2); while(min_n > 0) { each_digit_min = min_n % 10; each_digit_max = max_n % 10; if(each_digit_min + each_digit_max + carry > 9) { iRet++; carry = 1; } else carry = 0; min_n /= 10; max_n /= 10; } while(carry == 1 && max_n > 0) { each_digit_max = max_n % 10; if(each_digit_max == 9) iRet++; else break; max_n /= 10; } return iRet; } int main() { #ifdef _UNITTEST UnitTest::RunAllTests(); #endif //_UNITTEST int n1, n2; std::vector<int> vResult; while(cin >> n1 >> n2) { if(n1 == 0 && n2 == 0) break; vResult.push_back(GetPrimaryArithmetic(n1, n2)); } if(vResult.size() > 0) { for(int i = 0; i < vResult.size(); i++) { if(vResult[i] == 0) cout << "No" << " carry operation." << endl; else cout << vResult[i] << " carry operation." << endl; } } return 0; } #ifdef _UNITTEST //TEST(testSetUp) //{ //} //TEST(testTearDown) //{ //} TEST(testGetPrimaryArithmetic_1and1) { CHECK_EQUAL(0, GetPrimaryArithmetic(4, 5)); CHECK_EQUAL(1, GetPrimaryArithmetic(5, 5)); CHECK_EQUAL(0, GetPrimaryArithmetic(0, 0)); CHECK_EQUAL(1, GetPrimaryArithmetic(9, 9)); CHECK_EQUAL(0, GetPrimaryArithmetic(-1, -1)); CHECK_EQUAL(0, GetPrimaryArithmetic(0, 1)); } TEST(testGetPrimaryArithmetic_1and2) { CHECK_EQUAL(1, GetPrimaryArithmetic(55, 5)); CHECK_EQUAL(2, GetPrimaryArithmetic(95, 5)); } TEST(testGetPrimaryArithmetic_multi) { CHECK_EQUAL(3, GetPrimaryArithmetic(999, 9)); CHECK_EQUAL(4, GetPrimaryArithmetic(9999, 9)); } #endif //_UNITTEST
-
-
Wrong Answer 라는군요. 냠... 어떤 case 가 문제가 된 걸까요?
- carry operations 을 carry operations. 으로 수정하셔야 할듯 ^^;
-
그나저나 수안씨 C++ syntax 언제 해줄껴~~
/* @JUDGE_ID:parkpd 10038 C "test" */ /* @BEGIN_OF_SOURCE_CODE */ #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #define _CRT_SECURE_NO_DEPRECATE 1 #include <stdlib.h> #include <iostream> #include <vector> #include <set> #include <deque> #include <strstream> #include <algorithm> using namespace std; //#define _UNIT_TEST #ifdef _UNIT_TEST #include "../../UnitTest++/src/UnitTest++.h" int main() { UnitTest::RunAllTests(); char temp; cin >> temp; return 0; } #endif class CPrimaryArithmetic { public: static int GetCarryCount(int left, int right); static void GetInts(int num, vector<int>& nums); }; int CPrimaryArithmetic::GetCarryCount( int left, int right ) { vector<int> lefts; vector<int> rights; GetInts(left, lefts); GetInts(right, rights); int carryCount = 0; int additionalCarry = 0; for (int i = 9; i >= 0; --i) { if (10 <= lefts[i] + rights[i] + additionalCarry) { carryCount++; additionalCarry = 1; } } return carryCount; } // string 으로 하는 거랑 속도 비교해 볼 것. void CPrimaryArithmetic::GetInts( int num, vector<int>& nums ) { nums = vector<int>(10, 0); int index = 9; while (10 <= num) { nums[index] = (num % 10); num /= 10; --index; } nums[index] = num; } #ifndef _UNIT_TEST int main() { vector<pair<int, int> > testNums; while(1) { int left, right; cin >> left >> right; if ((0 == left) && (0 == right)) { break; } testNums.push_back(make_pair<int, int>(left, right)); } int count = (int)testNums.size(); for (int i = 0; i < count; ++i) { int carryCount = CPrimaryArithmetic::GetCarryCount(testNums[i].first, testNums[i].second); if (0 == carryCount) { cout << "No carry operation.\n"; } else if (1 == carryCount) { cout << "1 carry operation.\n"; } else { cout << carryCount << " carry operations\n"; } } return 0; } #else struct FixturePrimaryArithmetic : public CPrimaryArithmetic { vector<int> nums; }; TEST_FIXTURE(FixturePrimaryArithmetic, GetInts) { int expect[] = {0, 0, 0, 0, 0, 1, 2, 3, 4, 5}; GetInts(12345, nums); CHECK_ARRAY_EQUAL(expect, nums, 10); } TEST_FIXTURE(FixturePrimaryArithmetic, GetCarryCount) { CHECK_EQUAL(0, GetCarryCount(1, 1)); CHECK_EQUAL(1, GetCarryCount(2, 9)); CHECK_EQUAL(9, GetCarryCount(999999999, 1)); CHECK_EQUAL(0, GetCarryCount(123, 456)); CHECK_EQUAL(3, GetCarryCount(555, 555)); CHECK_EQUAL(1, GetCarryCount(123, 594)); CHECK_EQUAL(0, GetCarryCount(123, 0)); CHECK_EQUAL(1, GetCarryCount(4821, 311)); CHECK_EQUAL(3, GetCarryCount(999, 1)); CHECK_EQUAL(4, GetCarryCount(99099, 1001)); } #endif /* @END_OF_SOURCE_CODE */