SKKU Discrete Mathematics

(Ch. 5, Introduction to Number Theory)

                                                       Prof : Sang-Gu Lee  at SKKU

 

http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm  Discrete Math Labs (실습실)

http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm  (강의실)

http://matrix.skku.ac.kr/2018-DM-QnA/                  (질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm  (문제풀이)

http://matrix.skku.ac.kr/2018-DM-PBL/      (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/  (PBL report Eng, 영문 보고서)

 

DM Ch. 3, Functions, Sequences, and Relations

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-3/
DM-Ch-3-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html 
DM Ch. 3, 동영상강의 
Functions, Sequences, and Relations 1
  https://youtu.be/MhM_9ZuGAis 
Functions, Sequences, and Relations 2  https://youtu.be/ZjAtN9HkZwM
Functions, Sequences, and Relations 3  https://youtu.be/Uuwsx2aiEPI

 

Midterm Exam Solutions : https://youtu.be/iAfQCycd6ac


 

유형

Q & A

제목

P198 problem13

참여자

 Answered by 칭기즈, finalized by 전종문, refinalized by 백선민

질문

Q. Is the relation

{(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}

an equivalence relation on {1,2,3,4}? Explain.

답변

A.

Let, R = {(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}= {1,2,3,4}.

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_174829.PNG 

 

1. X, (x,x) R     (1,1),(2,2),(3,3),(4,4)     

     R  is reflexive (a loop at every vertex).

 

2. (x,y) R ,(y,x) R ​​​    (1,2),(2,1) / (1,1) / (2,2) / (3,3) / (4,4) 

     R  is symmetric (for every directed edge from v to w, there is a directed edge from w to v).

 

3. (x,y) R ,(y,z) R  are (x,z) R   (1,2) (2,1) are (1,1) / (1,2)(2,2)  are (1,2) / (1,1)(1,2) are (1,2)  / (2,2)(2,1) are (2,1) 

 R  is transitive (there is a directed edge from x to y and a directed edge from y to z , there is a directed edge from x to z).

R  is reflexive, symmetric, and transitive.

 

{(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)} is an equivalence relation on {1,2,3,4}.

 

 

 

 

 

 

 

 

 

유형

Q & A

제목

Problem 6(Computer Exercises)

참여자

Solved by 칭기즈 Revised by 김정주 Finalized by 김희성

Final OK by SGLee

 

답변

Discussion

For 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC10F7.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1108.gif are in the domain of the sequence.

설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1109.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC110A.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC111A.gif   sequence 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC111B.gif is increasing 

 Solution

Python code:

A=[int(x) for x in input("enter a sequence of

numbers:\n").split()]

count=1

count1=1

for i in range(len(A)-1):

count+=1

if A[i]<A[I+< span="">1]:</A[I+<>

count1+=1

if count==count1: 

print("increasing")

else:

print("not increasing")

Examples:

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184138.PNG
because second and third elements are 2 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184205.PNG 

 --------------------------------------

When we check whether the given sequence is increasing, we have to check  설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1109.gif.

But if n such that    설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC110A.gif is not true, then we can tell it is not increasing.

So if we find   n such that    설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC110A.gif is not true, we quickly exit and print "not increasing".

 If our program execute all n with all loops, and it doesn't find any exception, then we will print " increasing".

Our syntax for that argument can be seen in the line 6.

Our modified code is as following.

import sys

A=[int(x) for x in input("enter a sequence of numbers:\n").split()]

for i in range(len(A)-1):

  if A[i]>=A[i+1]:

    print("not increasing")

    sys.exit(0)

print("increasing") 

 

유형

Q & A

제목

Problem 9(Computer Exercises)

참여자

Solved by 칭기즈 Finalized by 전종문 Re-Finalized by 칭기즈

질문

Q Write a program that tests whether A is nondecreasing

답변

A.

Discussion

 For 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC10F7.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1108.gif are in the domain of the sequence.

설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC113F.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1140.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1151.gif   sequence 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1152.gif is nondecreasing

 increasing is replaced by nondecreasing : 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1176.gif is replaced by 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1177.gif 

Solution:

Python code

A=[int(x) for x in input("enter a sequence of numbers:\n").split()]

count=1

count1=1

for i in range(len(A)-1):

  count+=1

  if A[i]<=A[i+1]:

    count1+=1

if count==count1:

  print("nondecreasing")

else:

  print("not nondecreasing")

Right Example

 설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_185222.PNG

Wrong example

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_185253.PNG  

C code:

#include <stdio.h>

int A[10000000], N, answer = 1;

int main()

{

printf("Enter the number of sequence: ");

scanf("%d", &N);

printf("Enter a sequence: ");

for (int i = 1; i < N; i++) { scanf("%d", &A[i]);}

for (int i = 1; i < N; i++) {

if (A[i - 1] > A[i]) { answer = -1; break; }

}

if (answer == 1) {

printf("nondecreasing\n");

}

else

{

 printf("not nondecreasing\n");

}

return 0;

}

 

 

 

 

유형

Q & A

제목

Problem 20

참여자

Solved by 오동찬 Finalized by Muhammad/모하메드​ 

Re-Finalized by 오동찬  Final OK by SGLee

질문

Q. Use the result of Exercise 19 to find the matrix of the relation R₂° R.

+) Result of Exercise 19

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/5ehdcks/2018_09_29_133218.JPG 

답변

A.

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/5ehdcks/2018_09_30_111114.JPG

 

 

 

 

 

 

 

 

 

 

 

 

유형

Q & A

제목

Problem 19

참여자

Solved by 오동찬 Finalized by 만우흠 Re-Finalized by 오동찬

질문

Q. Use the result of Exercise 19 to find the matrix of the relation R₂° R.

+) Result of Exercise 19

 Find the matrix product AA.

답변

A.

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/5ehdcks/2018_09_30_111913.JPG

 


 

유형

Q & A

제목

Problem 18

참여자

Solved by 만우흠 Date: 2018.09.28 Finalized by 서명원 Date: 2018.09.29

Final OK by SGLee ​

질문

Q. Exercises 18 and 19 refer to the sequence c1,c2, defined by the equations.

설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\E809A9DB.tmp

답변

A.

When put n=2,

 2C2/2+2 = 2C1 +2 = 2C1 +2 = 0+2 = 2    (because C1 = 0)

 Therefore, C2=2

When put n=3,

 2C​​​3/2+2 = 2C1.5+3 = 2C1+3 = 0+3 = 3 (because C1.5 = C1 = 0)

 Therefore, C3=3

When put n=4,

 2C4/2​​+4 = 2C2+4 = 2C2+4 = 2*2+4=8 (because C2 = 2)

 Therefore, C4=8

When put n=5,

 2C5/2​​+5 = 2C2.5+5 = 2C2+5 =2*2+5 = 9 (because C2.5 = C2 = 2)

 Therefore, C5=9

Solution:  C2=2, C3=3, C4=8, C5=9.    

 


 

유형

Q & A

제목

Problem 17

참여자

Solved by 만우흠 Date: 2018.09.28  Finalized by 서명원 Date: 2018.09.29

Final OK by SGLee

질문

Q. Exercises 17-20 refer to the relations

R1 = {(1,x),(2,x),(2,y),(3,y)}

R2 = {(x,a),(x,b),(y,a),(y,c)}

17. Find the matrix A1 of the relation R1 relative to the orderings

1, 2, 3; x, y.

답변

A.

Let x={1,2,3}, y={x, y}

and R1={(1, x),(2, x), (2, y), (3, y)}

A1 = 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/wanyuxin/2018_09_28_194302.png 

 


 

유형

Q & A

제목

Problem 16

참여자

Solved by 김은율 Finalized by ​유가이 올렉산드르 Final OK by SGLee 

질문

Let R be the relation defined on the set of eight-bit strings by s1 R s2 provided that s1 and s2 have the same number of zeros.

(a) Show that R is an equivalence relation.
(b) How many equivalence classes are there?
(c) List one member of each equivalence class.

답변

A.

(a) R is reflexive because any eight-bit string has the same number of zeros as itself.

     R is symmetric because, if s1 and s2 have the same number of zeros, then s  and s1 have the same number of zeros.

    R is transitive. [Proof) Suppose that s1 and s2 have the same number of zeros and that s2 and s3 have the same number of zeros. Then s1 and s3 have the same number of zeros.]

     Therefore, R is an equivalence relation.

 (b) There are nine equivalence classes.  (the set of eight-bit strings, The number of zeros can be   0, 1, 2, 3, 4, 5, 6, 7, 8)

Small Supplement: You are right. There are nine equivalence classes - the class of strings with no zeros, the class of strings with 1 zero, the class of strings with 2 zeroes and so on. The number of zeros can be   0, 1, 2, 3, 4, 5, 6, 7, 8, so we have nine equivalence classes in general.

(c) And now we can list one member of each equivalence class

      11111111   is the only member of the class with no zeros.

      11111110   is a member of the class with 1 zero.

      11111100   is a member of the class with 2 zero.

      11111000   is a member of the class with 3 zero.

      11110000   is a member of the class with 4 zero.

      11100000   is a member of the class with 5 zero.

      11000000   is a member of the class with 6 zero.

      10000000   is a member of the class with 7 zero

      00000000   is a member of the class with all zero members. ■

 

유형

Q & A

제목

Problem 15

참여자

Solved by 정호진 Finalized by 엄자균 Final OK by SGLee

질문

Q. Find the equivalence relation (as a set of ordered pairs) on {a, b, c, d, e} whose equivalence classes are {a}, {b, d, e}, {c}.

답변

A.

Given set is {a, b, c, d, e}.   Let R be an equivalence relation whose equivalence classes are {a}, {b, d, e}, {c}

where

[a] = {a/(a,a) R}

 [b] = [d] = [e] = {x/(b,x), (d,x), (e,x) R} = {b, d, e}   

 [c] = {c/(c,c) R }

=> R {(a,a), (b,b), (d,b), (e,b), (b,d), (d,d), (e,d), (b,e), (d,e), (e,e), (c,c) } ,  is an equivalence relation.

 


 

유형

Q & A

제목

Problem 14

참여자

solved by 서명원finalized by 오동찬 Final OK by SGLee​

질문

Q. Given that the relation

{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)}

is an equivalence relation on {1,2,3,4}, find [3], the equivalence class containing 3. How many (distinct) equivalence classes are there? 

답변

A.

Draw graph with above problem set.

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/tjauddnjs/2018_09_27_184931.jpg

In the graph above, we can see that we have two possible set can go to {3}.

So, [3] = {3,4} =[4]  and [1] = {1, 2} =[2] . 

There are two equivalence classes.

 

 

 

 

 

유형

Q & A

제목

Problem 11

참여자

Solved by 정호진 Finalized by 칭기즈 Final OK by TA  2018.10.02​

질문

Q. Give an example of a relation on {1, 2, 3, 4} that is reflexive, not antisymmetric, and not transitive.

답변

A.

reflexive: (x,x)  R for every x ∈​ X

antisymmetric: for all x, y ∈​ X, if (x,y) ∈​ R and (y,x) ∈​ R, then x=y

transitive: for all x, y, z ∈​ X, if (x,y) and (y,z) ∈​ R, then (x,z) ∈​ R

So, (1,1), (2,2), (3,3), (4,4) ∈​ R (Reflexive)

(2,3), (3,2)  ​​R (not antisymmetirc)

(1,2) ​∈​ R (not transitive)

R = {(1,1), (2,2), (3,3), (4,4), (2,3), (3,2), (1,2)}

Digraph:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_02_103545.PNG

1. Every vertex has a loop so

 R is reflexive

2. (2,3) (3,2)  ​​R:Directed line from 2 to 3 , Directed line from 3 to 2 but x≠y

 R is not antisymmetric

3.(1,2),(2,3)  ​​R Directed line from 1 to 2, Directed line from 2 to 3 but there is no line from 1 to 3

R is not transitive

 


 

유형

Q & A

제목

Problem 10

참여자

Solved by 김정주 Date:2018.09.30 Finalized by 칭기즈 Date:2018.09.30​

Re-Finalized by 전종문 Date:2018.09.30 Final OK by SGLee

질문

Q In Exercises 9 and 10, determine whether the relation defined on the set of positive integers is reflexive, symmetric, antisymmetric, transitive, and/or a partial order.

10. (x,y)R if 3 divides x + y

답변

A.

*   (1,1) R   R  is not reflexive

*   If  3|+y  then  3|+x   R  is symmetric

*   R  is symmetric but R  is not reflexive   R is not antisymmetric

*   (1,2)R(2,1)R ⇒​  (1,1)   R  is not transitive

 R is antisymmetric, transitive but R is not reflexive  R is not a partial order

R is symmetric, not reflexive, not antisymmetric, not transitive, not a partial order

 


 

유형

Q & A

제목

Problem 8

참여자

Solved by 엄자균 Date 2018.09.27 Revised by 정호진 Date 2018.09.28

Finalized by 전종문 Date 2018.09.28 Final OK by SGLee

질문

Q 8. Let α = ccddc and β = c³d². Find

 (a) αβ   (b) βα   (c) |α|   (d) |ααβα

답변

A.

α ccddc , β = c³d² =cccdd

(a) αβ  = ccddccccdd

(b) βα  = cccdd​​ccddc

(c) |α|=  |ccddc| = 5

(d) |ααβα|= |ccddcccddccccdd​​ccddc| =  20

Answer  (a) αβ ccddccccdd​​  (b) βα  = cccdd​​ccddc  (c)  |α|= 5  (d) |ααβα| =  20

 


 

유형

Q & A

제목

Problem 7

참여자

Solved by 유가이 올렉산드르 Finalized by 오동찬 Final OK by SGLee 

질문

Q Let

bn = 설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\785C740C.tmp.

   (a) Find b5 and b10 

   (b) Find a formula for bn  

   (c) Is bn  increasing?

   (d) Is bn  decreasing?

답변

A.

(a)  b5  = (1+1)2  12 + (2+1)2  22 + (3+1)2  32 + (4+1)2  42+ (5+1)2  52 = 35;

b10  = (1+1)2  12 + (2+1)2  22 + (3+1)2  32 + (4+1)2  42 + +(5+1)2  52 +…… + (9+1)2  92 + (10+1)2  102 = 120;  

(b) bn = (1+1)2  12 + (2+1)2  22 ++ (in+1)2  in2;

        bn = 설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\257651FA.tmp = 설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\A55B5C18.tmp 

 =   설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\4BC1D1E6.tmp = 설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\3ECB9EE4.tmp = n(2+n) = 2n + n2 = 설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\DF7F3A92.tmp+ 2n + 1 1

 = (n+1)2  1;       ■

(c)  Yes, because b< bn+1 , for all n which n and n+1 are in domain of the sequence. ■

(d)  No, because bn > bn+1 (bn is no bigger than bn+1), for all n which n and n+1 are in domain of the sequence. Or, since we show that bn  is increasing in question (c), so bn  is not decreasing. 

 


 

유형

Q & A

제목

Problem 6

참여자

solved by 엄자균 revised by 오동찬 Finalized by 오동찬 Final OK by SGLee 

질문

 

답변

A.

설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\72AB4434.tmp

설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\D70C1C62.tmp

설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\54BB5AC0.tmp

설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\5E654ECE.tmp

 


 

유형

Q & A

제목

Problem 5

참여자

solved by 칭기즈 finalized by 신혜수 Final OK by SGLee

질문

For the sequence a defined by = 2*n + 2, find   

(a)

(b)

(c)

답변

A.설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_201550.PNG

Solution :

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/gptntls/2018_09_29_135854.png

The answer:

a) 14

b) 18

c) 192

 

 

 

 

 

유형

Q & A

제목

Problem 4

참여자

Solved by 오동찬 Date: 2018.09.27 Finalized by 서명원 Date: 2018.09.27 Re-Finalized by 오동찬 Date: 2018.09.29

Final OK by TA Date :  2018. 10. 02

질문

Q For the Hash function (https://en.wikipedia.org/wiki/Hash_function)

                     h(x) = x  mod 13,

show how the data 

784, 281, 1141, 18, 1, 329, 620, 43, 31, 684

would be inserted in the order given in initially empty cells indexed 0 to 12.  

+) In hash function, my using modulo operation, we can get output h(x) by input x. This means that we can index inputs to different outputs. Additionally, by choosing modulo number, in this case 13, we can put data to certain range of indexed(in this case 13-1 = 12 cases). 

So, in this problem we get hash outputs(empty cells) from given data and stored them to 13 different empty cells.

답변

A.

By mod operation, we insert data as an x and get h(x) (or y) result.

(x,y means "store item x in cell y.")

 (784, 4), (281, 8), (1141,10) (18,5), (1,1), (329, 6), (620, 9), (43, 7), (31, 11), (684,12)   

Hashing variable-length data[https://en.wikipedia.org/wiki/Hash_function)

When the data values are long (or variable-length) character strings—such as personal names, web page addresses, or mail messages—their distribution is usually very uneven, with complicated dependencies. For example, text in any natural language has highly non-uniform distributions of characters, and character pairs, very characteristic of the language. For such data, it is prudent to use a hash function that depends on all characters of the string—and depends on each character in a different way.

In cryptographic hash functions, a Merkle–Damgård construction is usually used. In general, the scheme for hashing such data is to break the input into a sequence of small units (bitsbyteswords, etc.) and combine all the units b[1], b[2], …, b[m] sequentially, as follows

S ← S0;                         // Initialize the state.

for k in 1, 2, ..., m do        // Scan the input data units:

  S ← F(S, b[k]);               // Combine data unit k into the state.

return G(S, n)                  // Extract the hash value from the state. 

This schema is also used in many text checksum and fingerprint algorithms. The state variable S may be a 32- or 64-bit unsigned integer; in that case, S0 can be 0, and G(S,n) can be just S mod n. The best choice of F is a complex issue and depends on the nature of the data.  

 

 


 

유형

Q & A

제목

Problem 3

참여자

Solved by 유가이 올렉산드르 inalized by 유가이 올렉산드르 Final OK by SGLee

질문

Give examples of functions f and g such that fg   is onto, but g is not onto.

답변

A.

Define f: {0,1}{0} by f (0) = f (1) = 0, and g: {0}{0,1} by g (0) = 0.

Then g is not onto because there is no preimage in the domain {0} of the value 1 which is in its range.

 But fis onto.  

( because fg  : {0}{0}  by   fg  (0) = f (0) = 0. which is a trivial bijective function.)                                                              

 


 

유형

Q & A

제목

Problem 2

참여자

Solved by 유가이 올렉산드르, Date: 2018.09.30 Finalized by 오동찬, Date: 2018.09.30 Final OK by SGLee

질문

Find real numbfloor(x) * floor(y) = floor(xy) – 1

답변

A.

 By definition, the floor of x, denoted 설명: C:\Users\영은\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\7BA79569.tmp, is the greatest integer less than or equal to x.

 Therefore, we must choose two numbers (x and y), that satisfy the conditions floor(x) * floor(y) < floor(xy) -1. This means that when we multiply two numbers, their result should be unless '1' bigger then floor(x) * floor(y).

 We may choose real numbers x=2.3 and y=5.1. 

Since floor(2.3)  = 2 and floor(5.3)  = 5,

LHS = floor(x) * floor(y) becomes 10

 Since floor(xy) = floor(12.19) = 12 ,

RHS becomes 12-1 = 11.

We have found real numbers x=2.3 and y=5.1 satisfying

floor(x) * floor(y) = floor(xy) – 1  

 

 

 

 

 

 

 

 

 

 

코딩관련 solve 문제들

유형

Q & A

제목

Ch 3 Problem 1

참여자

Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23

질문

Implement a hashing system for storing integers in an array.

답변

#include

#include

int main()

{

           int num;

           printf("배열원소의 갯수를 입력하시오 : ");

           scanf_s("%d", &num);

           printf("배열을 입력하시오 : ");

           int *arr = (int*)malloc(sizeof(int)*num);             //배열 동적할당

           for (int i = 0; i < num; i++) {

                     scanf_s("%d", &arr[i]);                        //반복문을 통한 배열입력

           }

           for (int i = 0; i < num; i++) {

                     printf("%d", arr[i]);

                     if (i != num - 1)

                                printf(" , ");

                     else

                                printf("\n");

           }

           free(arr);

}

          

comment

 

Hash function

A hash function is any function that can be used to map data of arbitrary size to data of a fixed size.

해쉬 시스템에 대해서 공부하게 되었고, 해쉬함수가 무엇인지 알게 되었습니다.

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_173324.PNG
설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_173422.PNG

 

 

 

 

유형

Q & A

제목

Ch 3 Problem 3

참여자

Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23

질문

Write a program that generates pseudorandom Integers.

pseudorandom : 의사난수

답변

#include

int main() 

{

           int num = rand();

           for(int i =0;i<5;i++)

           printf("생성된 의사 난수 : %d\n", rand());

           return 0;

}

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_173937.PNG

but we can make Time-dependent random numbers.(Not pseudorandom)

 

#include

#include

int main()

{

           srand((int)time(NULL));

           for(int i=0;i<5;i++)

           printf("생성된 난수 : %d\n",rand());  

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_174223.PNG

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_174253.PNG Comment

Pseudo random number(의사 난수)

의사 난수란 컴퓨터에 의해 만들어지는 난수로서. (어떤 유한 개수의 조립된 수의 주기성 없는 계열을 난수라 한다) 산술 난수를 컴퓨터에 발생시키면 커다란 주기를 가지게 되는데 이와 같이 진정한 의미로는 난수가 아니지만 사용상 난수로 간주해도 지장이 없는 난수를 의사 난수라고 한다.

의사 난수를 무엇인지 이해했고 이를 이용해 문제를 풀어볼 수 있었다.

유형

Q & A

제목

Ch 3 Problem 8

참여자

Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23

질문

Write a program that tests whether A is nonincreasing

답변

#include

#include

int main()

{

           int num, count = 1;

           printf("배열원소의 갯수를 입력하시오 : ");

           scanf_s("%d", &num);

           printf("배열을 입력하시오 : ");

           int *arr = (int*)malloc(sizeof(int)*num);            //동적할당

           for (int i = 0; i < num; i++) {

                     scanf_s("%d", &arr[i]);                      //반복문을 통한 배열 입력

           }

           for (int i = 1; i < num; i++) {

                     if (arr[i - 1] >= arr[i])                        //증감확인

                                count -= 1;

           }

           if (count == 1)

                     printf("increasing\n");

           else

                     printf("nonincreasing\n");

           free(arr);              

}

 

1.increasing

설명: http://www.icampus.ac.kr/front/study/QnaAction.do?method=view&lmsBdotSeq=2811566&lmsBlbdId=376656&isRply=Y
 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_174802.PNG
 

2.nonincreasing

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_174914.PNG

 

유형

Q & A

제목

Ch 3 Problem 11

참여자

Solved by 김희성 2018.11.18 Finalized by 전수호 2018.11.23

질문

Write a program to determine whether one string is a sub-string of another string.

답변

#include

#include

int main()

{

           int num, num1, count = 0, i, j;

           printf("one string의 갯수를 입력하시오 : ");

           scanf_s("%d", &num);

           int *arr1 = (int*)malloc(sizeof(int)*num);

           printf("one string을 입력하시오 : ");                         //one string 입력

           for (i = 0; i < num; i++) {

                     scanf_s("%d", &arr1[i]);

           }

           printf("sub string의 갯수를 입력하시오 : ");

           scanf_s("%d", &num1);

           int *arr2 = (int*)malloc(sizeof(int)*num1);

           printf("sub string을 입력하시오 : ");

           for (i = 0; i < num1; i++) {

                     scanf_s("%d", &arr2[i]);

           }

           for (i = 0; i < num1; i++) {

                     for (j = 0; j < num; j++) {

                                if (arr1[j] == arr2[i])

                                          count += 1;

                     }

           }

           if (count >= num1)

                     printf("sub string\n");

           else

                     printf("non-sub string\n");

           free(arr1);

           free(arr2);

}              

1.Sub string

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_180323.PNG

2. Non-sub string

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_18_180221.PNG
 

Comment 

Sub string에 대해서 알게 되었고, 코딩과 수학 사이 관계에 대해서 이해도가 한층 깊어졌습니다.

Final team project 대한 comment

7조의 인원은 리더인 저까지 5명으로 조원은 정영기, 김문서, 김호준, 전수호입니다.  7조는 ch3 맡게 되었습니다. 기본적으로 모든 문제는 전체 학생들이 토론하면서 풀었고,

그것을 모아서 완성하고 정리하여 보고 드립니다.

각각 맡은 역할은 김희성 : finalize선언 되지 않은 문제들 solve,

전수호 : finalize선언 되지 않은 문제들 finalize선언, 김문서 : finalize선언된 문제들 타이핑, 정영기 : ch3 관련 자료 조사, 김호준 : 팀프로젝트 발표 이렇게 나누었습니다. 하지만 발표를 기한이 되자 단톡방에 있던 김호준 씨가 연락이 두절되었습니다. 그래서 발표는 제가 맡도록 하겠습니다.

 

…   학기동안 학생들의 많은 질문에 일일이 대답해 주시느라 고생 많으셨고 감사드립니다!!

 

 

 

 

(The End of Ch 3)

 

Copyright @ 2018 SKKU Matrix Lab. All rights reserved.

Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee

*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).