1
00:00:00,000 --> 00:00:02,826
>> [CHWARAE CERDDORIAETH]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Felly fath gosod yn un arall
algorithm gallwn ei ddefnyddio i ddatrys arae.

4
00:00:09,370 --> 00:00:12,350
Y syniad y tu ôl i algorithm hwn
yw i adeiladu eich array ddidoli

5
00:00:12,350 --> 00:00:19,670
yn eu lle, gan symud elfennau y tu allan i
y ffordd wrth i chi fynd, i wneud lle.

6
00:00:19,670 --> 00:00:22,240
Mae hyn ychydig yn wahanol
o fath dethol neu swigod

7
00:00:22,240 --> 00:00:25,460
didoli, er enghraifft, lle
rydym yn addasu y lleoliadau,

8
00:00:25,460 --> 00:00:26,910
lle rydym yn gwneud cyfnewidiadau.

9
00:00:26,910 --> 00:00:29,760
>> Yn yr achos hwn yr hyn rydym yn mewn gwirionedd
wneud yw elfennau symudol

10
00:00:29,760 --> 00:00:31,390
drosodd, allan o'r ffordd.

11
00:00:31,390 --> 00:00:34,030
Sut mae algorithm hwn
gweithio mewn pseudocode?

12
00:00:34,030 --> 00:00:37,646
Wel gadewch i ni jyst fympwyol dweud bod y
Elfen gyntaf y rhesi yn cael ei datrys.

13
00:00:37,646 --> 00:00:38,770
Rydym yn adeiladu yn ei lle.

14
00:00:38,770 --> 00:00:42,660
>> Rydym yn gonna yn mynd un elfen ar y tro a
adeiladu, ac felly y peth cyntaf a welwn

15
00:00:42,660 --> 00:00:43,890
yn un elfen arae.

16
00:00:43,890 --> 00:00:47,720
A thrwy ddiffiniad, yn un
Elfen amrywiaeth yn cael ei datrys.

17
00:00:47,720 --> 00:00:50,850
>> Yna byddwn yn ailadrodd y broses hon until--
byddwn yn ailadrodd y broses ganlynol

18
00:00:50,850 --> 00:00:52,900
nes bod yr holl elfennau yn cael eu datrys.

19
00:00:52,900 --> 00:00:57,770
Edrychwch ar yr elfen heb eu didoli nesaf ac
mewnosod i mewn y rhan ddidoli,

20
00:00:57,770 --> 00:01:01,209
drwy symud y nifer gofynnol
o elfennau allan o'r ffordd.

21
00:01:01,209 --> 00:01:03,750
Gobeithio delweddu hwn
Bydd yn eich helpu i weld yn union beth sydd

22
00:01:03,750 --> 00:01:05,980
mynd ymlaen gyda'r math fewnosod.

23
00:01:05,980 --> 00:01:08,010
>> Felly eto, dyma ein
array heb eu didoli cyfan,

24
00:01:08,010 --> 00:01:10,970
yr holl elfennau a nodir mewn coch.

25
00:01:10,970 --> 00:01:13,320
A gadewch i ni ddilyn y
camau ar ein pseudocode.

26
00:01:13,320 --> 00:01:16,970
Y peth cyntaf a wnawn, yn cael ei alwn y
Elfen gyntaf y rhesi, didoli.

27
00:01:16,970 --> 00:01:20,920
Felly rydym yn unig lais gonna
pump, rydych yn datrys erbyn hyn.

28
00:01:20,920 --> 00:01:24,570
>> Yna, rydym yn edrych ar y nesaf
Elfen heb eu didoli y rhesi

29
00:01:24,570 --> 00:01:27,610
ac yr ydym am i fewnosod bod
i mewn i'r gyfran didoli,

30
00:01:27,610 --> 00:01:29,750
drwy symud elfennau drosodd.

31
00:01:29,750 --> 00:01:33,470
Felly ddau yw heb eu didoli y nesaf
elfen y rhesi.

32
00:01:33,470 --> 00:01:36,250
Yn amlwg mae'n perthyn gerbron y
pump, felly yr hyn yr ydym yn gonna ei wneud

33
00:01:36,250 --> 00:01:41,580
yn fath o cynnal dau o'r neilltu am eiliad,
sifft pump drosodd, ac yna rhowch dau

34
00:01:41,580 --> 00:01:43,210
cyn pump, ble i fynd.

35
00:01:43,210 --> 00:01:45,280
Ac yn awr gallwn ddweud bod dau yn cael ei datrys.

36
00:01:45,280 --> 00:01:48,400
>> Felly, fel y gwelwch, mae gennym dim ond hyd yn hyn
edrych ar ddwy elfen y rhesi.

37
00:01:48,400 --> 00:01:50,600
Nid ydym wedi edrych ar y
gorffwys o gwbl, ond rydym wedi

38
00:01:50,600 --> 00:01:54,582
got rhai ddwy elfen trefnu yn ôl
ffordd y mecanwaith symud.

39
00:01:54,582 --> 00:01:56,410
>> Felly, rydym yn ailadrodd y broses eto.

40
00:01:56,410 --> 00:01:58,850
Edrychwch ar y heb eu didoli nesaf
Elfen, dyna un.

41
00:01:58,850 --> 00:02:04,010
Gadewch i ni ddal hynny o'r neilltu am eiliad,
symud popeth drosodd, a rhowch un

42
00:02:04,010 --> 00:02:05,570
lle y dylai fynd.

43
00:02:05,570 --> 00:02:08,110
>> Unwaith eto, yn dal, rydym wedi dim ond erioed
edrych ar un, dau, a phump.

44
00:02:08,110 --> 00:02:12,480
Nid ydym yn gwybod beth arall yn dod,
ond rydym wedi datrys tair elfen hynny.

45
00:02:12,480 --> 00:02:16,030
>> Elfen heb eu didoli nesaf yw
tri, felly byddwn yn gosod o'r neilltu.

46
00:02:16,030 --> 00:02:18,200
Byddwn yn newid dros yr hyn yr ydym
Mae angen sydd, y tro hwn

47
00:02:18,200 --> 00:02:21,820
Nid yw popeth fel yn yr blaenorol
dau achos, dim ond y pum.

48
00:02:21,820 --> 00:02:25,440
Ac yna byddwn yn cadw tri yn,
rhwng y ddau a'r pump.

49
00:02:25,440 --> 00:02:27,849
>> Chwech yw'r nesaf heb eu didoli
elfen i'r casgliad.

50
00:02:27,849 --> 00:02:31,140
Ac yn wir chwech yn fwy na phump, felly
Nid oes angen hyd yn oed i ni wneud unrhyw gyfnewid.

51
00:02:31,140 --> 00:02:35,710
Gallwn jyst tac chwe dde i'r
diwedd y gyfran didoli.

52
00:02:35,710 --> 00:02:38,270
>> Yn olaf, pedwar yn y
Elfen heb eu didoli diwethaf.

53
00:02:38,270 --> 00:02:42,060
Felly, byddwn yn gosod o'r neilltu, newid drosodd
yr elfennau y mae angen i symud drosodd,

54
00:02:42,060 --> 00:02:43,780
ac yna ei roi pedwar lle mae'n perthyn.

55
00:02:43,780 --> 00:02:46,400
Ac yn awr yn edrych, rydym wedi didoli
o'r holl elfennau.

56
00:02:46,400 --> 00:02:48,150
Sylwch â mewnosod
didoli, nid oedd gennym

57
00:02:48,150 --> 00:02:50,240
i fynd yn ôl ac ymlaen ar draws y rhesi.

58
00:02:50,240 --> 00:02:54,720
Byddwn ond yn mynd ar draws yr amrywiaeth
un tro, ac yr ydym yn symud pethau

59
00:02:54,720 --> 00:02:59,870
y byddem yn dod ar eu traws yn barod, er mwyn
i wneud lle ar gyfer yr elfennau newydd.

60
00:02:59,870 --> 00:03:02,820
>> Felly beth yw'r achos gwaethaf
senario gyda'r math fewnosod?

61
00:03:02,820 --> 00:03:05,090
Yn yr achos gwaethaf, mae'r
amrywiaeth yn ôl.

62
00:03:05,090 --> 00:03:11,180
Mae'n rhaid i chi symud pob un o'r elfennau n
hyd i swyddi n, bob tro yr ydym yn sengl

63
00:03:11,180 --> 00:03:12,880
gwneud mewnosod.

64
00:03:12,880 --> 00:03:15,720
Mae hynny'n llawer o symud.

65
00:03:15,720 --> 00:03:18,014
>> Yn yr achos gorau, mae'r
amrywiaeth yn cael ei ddidoli yn berffaith.

66
00:03:18,014 --> 00:03:20,680
Ac yn fath o fel hyn a ddigwyddodd
gyda pump a chwech yn yr enghraifft,

67
00:03:20,680 --> 00:03:23,779
lle y gallai rydym yn unig tac ymlaen
heb orfod gwneud unrhyw symud,

68
00:03:23,779 --> 00:03:24,820
byddem yn ei hanfod yn gwneud hynny.

69
00:03:24,820 --> 00:03:27,560
>> Os ydych yn dychmygu y bydd ein
arae yn un drwy chwech,

70
00:03:27,560 --> 00:03:29,900
byddem yn dechrau ffwrdd gan
datgan un yn cael ei datrys.

71
00:03:29,900 --> 00:03:33,300
Mae dau yn dod ar ôl un, felly y gallwn yn unig
dweud, OK, wel un a dau yn cael eu didoli.

72
00:03:33,300 --> 00:03:36,190
Tair dod ar ôl dwy felly, OK,
un a dau a thri yn cael eu didoli.

73
00:03:36,190 --> 00:03:39,590
>> Nid ydym yn gwneud unrhyw cyfnewidiadau, rydym yn
dim ond symud y llinell hon mympwyol

74
00:03:39,590 --> 00:03:42,460
rhwng didoli a heb eu didoli wrth i ni fynd.

75
00:03:42,460 --> 00:03:46,646
Mor effeithiol ag y gwnaethom yn yr enghraifft,
troi elfennau glas, wrth i ni fwrw ymlaen.

76
00:03:46,646 --> 00:03:48,270
Felly beth yw'r Rhedeg achos gwaethaf, felly?

77
00:03:48,270 --> 00:03:51,854
Cofiwch, os oes rhaid inni symud pob un o'r
yr elfennau n swyddi n bosibl,

78
00:03:51,854 --> 00:03:54,020
gobeithio sy'n rhoi i chi
syniad bod yr achos gwaethaf

79
00:03:54,020 --> 00:03:57,770
Rhedeg yn O Big n sgwâr.

80
00:03:57,770 --> 00:04:00,220
>> Os yw'r amrywiaeth yn berffaith
didoli, pob mae'n rhaid i ni wneud

81
00:04:00,220 --> 00:04:04,480
yn edrych ar bob elfen unigol
unwaith, ac yna rydym yn ei wneud.

82
00:04:04,480 --> 00:04:08,440
Felly, yn yr achos gorau, mae'n omega o n.

83
00:04:08,440 --> 00:04:09,490
>> Rwy'n Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Mae hyn yn CS50.

85
00:04:11,760 --> 00:04:13,119