<!doctype html>

sw_lab2.mdhtml {overflow-x: initial !important;}#write, body { height: auto; }
#write, #write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write ol, #write p, #write ul { position: relative; }
#write, #write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p, #write pre { width: inherit; }
#write, pre { white-space: pre-wrap; }
.CodeMirror, .md-fences, table { text-align: left; }
.md-reset, a:active, a:hover { outline: 0px; }
.md-reset, .md-toc-item a { text-decoration: none; }
.MathJax_SVG, .md-reset { float: none; direction: ltr; }
:root { --bg-color:#ffffff; --text-color:#333333; }
html { font-size: 14px; background-color: var(--bg-color); color: var(--text-color); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; -webkit-font-smoothing: antialiased; }
body { margin: 0px; padding: 0px; bottom: 0px; top: 0px; left: 0px; right: 0px; font-size: 1rem; line-height: 1.42857; overflow-x: hidden; background: inherit; }
.in-text-selection, ::selection { background: rgb(181, 214, 252); text-shadow: none; }
#write { margin: 0px auto; word-break: normal; word-wrap: break-word; padding-bottom: 70px; overflow-x: visible; }
.first-line-indent #write p .md-line { text-indent: 0px; }
.first-line-indent #write li, .first-line-indent #write p, .first-line-indent #write p .md-line:first-child { text-indent: 2em; }
.for-image #write { padding-left: 8px; padding-right: 8px; }
body.typora-export { padding-left: 30px; padding-right: 30px; }
@media screen and (max-width: 500px) {
body.typora-export { padding-left: 0px; padding-right: 0px; }
.CodeMirror-sizer { margin-left: 0px !important; }
.CodeMirror-gutters { display: none !important; }
}
#write > blockquote:first-child, #write > div:first-child, #write > ol:first-child, #write > p:first-child, #write > pre:first-child, #write > table:first-child, #write > ul:first-child { margin-top: 30px; }
#write li > table:first-child { margin-top: -20px; }
img { max-width: 100%; vertical-align: middle; }
button, input, select, textarea { color: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; font-size: inherit; line-height: inherit; font-family: inherit; }
input[type="checkbox"], input[type="radio"] { line-height: normal; padding: 0px; }
*, ::after, ::before { box-sizing: border-box; }
h1 { font-size: 2rem; }
h2 { font-size: 1.8rem; }
h3 { font-size: 1.6rem; }
h4 { font-size: 1.4rem; }
h5 { font-size: 1.2rem; }
h6 { font-size: 1rem; }
p { -webkit-margin-before: 1rem; -webkit-margin-after: 1rem; -webkit-margin-start: 0px; -webkit-margin-end: 0px; }
.mathjax-block { margin-top: 0px; margin-bottom: 0px; -webkit-margin-before: 0px; -webkit-margin-after: 0px; }
.hidden { display: none; }
.md-blockmeta { color: rgb(204, 204, 204); font-weight: 700; font-style: italic; }
a { cursor: pointer; }
sup.md-footnote { padding: 2px 4px; background-color: rgba(238, 238, 238, 0.7); color: rgb(85, 85, 85); border-radius: 4px; }
#write input[type="checkbox"] { cursor: pointer; width: inherit; height: inherit; }
#write > figure:first-child { margin-top: 16px; }
figure { overflow-x: auto; margin: -8px 0px 0px -8px; max-width: calc(100% + 16px); padding: 8px; }
tr { break-inside: avoid; break-after: auto; }
thead { display: table-header-group; }
table { border-collapse: collapse; border-spacing: 0px; width: 100%; overflow: auto; break-inside: auto; }
.CodeMirror-line, .md-fences { break-inside: avoid; }
table.md-table td { min-width: 80px; }
.CodeMirror-gutters { border-right: 0px; background-color: inherit; margin-right: 4px; }
.CodeMirror-placeholder { opacity: 0.3; }
.CodeMirror pre { padding: 0px 4px; }
.CodeMirror-lines { padding: 0px; }
div.hr:focus { cursor: none; }
.md-fences { font-size: 0.9rem; display: block; overflow: visible; white-space: pre; background: inherit; position: relative !important; }
.md-diagram-panel { width: 100%; margin-top: 10px; text-align: center; padding-top: 0px; padding-bottom: 8px; overflow-x: auto; }
.md-fences .CodeMirror.CodeMirror-wrap { top: -1.6em; margin-bottom: -1.6em; }
.md-fences.mock-cm { white-space: pre-wrap; }
.show-fences-line-number .md-fences { padding-left: 0px; }
.show-fences-line-number .md-fences.mock-cm { padding-left: 40px; }
.footnotes { opacity: 0.8; font-size: 0.9rem; margin-top: 1em; margin-bottom: 1em; }
.footnotes + .footnotes { margin-top: 0px; }
.md-reset { margin: 0px; padding: 0px; border: 0px; vertical-align: top; background: 0px 0px; text-shadow: none; position: static; width: auto; height: auto; white-space: nowrap; cursor: inherit; -webkit-tap-highlight-color: transparent; line-height: normal; font-weight: 400; text-align: left; box-sizing: content-box; }
.md-toc-inner, a img, img a { cursor: pointer; }
li div { padding-top: 0px; }
blockquote { margin: 1rem 0px; }
li .mathjax-block, li p { margin: 0.5rem 0px; }
li { margin: 0px; position: relative; }
blockquote > :last-child { margin-bottom: 0px; }
blockquote > :first-child { margin-top: 0px; }
.footnotes-area { color: rgb(136, 136, 136); margin-top: 0.714rem; padding-bottom: 0.143rem; white-space: nowrap; }
@media print {
body, html { border: 1px solid transparent; height: 99%; break-after: avoid; break-before: avoid; }
#write { margin-top: 0px; border-color: transparent !important; }
.typora-export * { -webkit-print-color-adjust: exact; }
h1, h2, h3, h4, h5, h6 { break-after: avoid-page; orphans: 2; }
p { orphans: 4; }
html.blink-to-pdf { font-size: 13px; }
.typora-export #write { padding-left: 1cm; padding-right: 1cm; padding-bottom: 0px; break-after: avoid; }
.typora-export #write::after { height: 0px; }
@page { margin: 20mm 0px; }
}
.footnote-line { margin-top: 0.714em; font-size: 0.7em; }
pre.md-meta-block { font-size: 0.8rem; min-height: 0.8rem; white-space: pre-wrap; background: rgb(204, 204, 204); display: block; overflow-x: hidden; }
p > img:only-child { display: block; margin: auto; }
.md-line > .md-image:only-child, p > .md-image:only-child { display: inline-block; width: 100%; text-align: center; }
.mathjax-block:not(:empty)::after, .md-toc-content::after, .md-toc::after { display: none; }
#write .MathJax_Display { margin: 0.8em 0px 0px; }
.mathjax-block { white-space: pre; overflow: hidden; width: 100%; }
p + .mathjax-block { margin-top: -1.143rem; }
[contenteditable="true"]:active, [contenteditable="true"]:focus { outline: 0px; box-shadow: none; }
.md-task-list-item { position: relative; list-style-type: none; }
.task-list-item.md-task-list-item { padding-left: 0px; }
.md-task-list-item > input { position: absolute; top: 0px; left: 0px; margin-left: -1.2em; margin-top: calc(1em - 10px); }
.math { font-size: 1rem; }
.md-toc { min-height: 3.58rem; position: relative; font-size: 0.9rem; border-radius: 10px; }
.MathJax_SVG, .mathjax-block .MathJax_SVG_Display { text-indent: 0px; max-width: none; max-height: none; min-height: 0px; }
.md-toc-content { position: relative; margin-left: 0px; }
.md-toc-item { display: block; color: rgb(65, 131, 196); }
.md-toc-inner:hover { }
.md-toc-inner { display: inline-block; }
.md-toc-h1 .md-toc-inner { margin-left: 0px; font-weight: 700; }
.md-toc-h2 .md-toc-inner { margin-left: 2em; }
.md-toc-h3 .md-toc-inner { margin-left: 4em; }
.md-toc-h4 .md-toc-inner { margin-left: 6em; }
.md-toc-h5 .md-toc-inner { margin-left: 8em; }
.md-toc-h6 .md-toc-inner { margin-left: 10em; }
@media screen and (max-width: 48em) {
.md-toc-h3 .md-toc-inner { margin-left: 3.5em; }
.md-toc-h4 .md-toc-inner { margin-left: 5em; }
.md-toc-h5 .md-toc-inner { margin-left: 6.5em; }
.md-toc-h6 .md-toc-inner { margin-left: 8em; }
}
a.md-toc-inner { font-size: inherit; font-style: inherit; font-weight: inherit; line-height: inherit; }
.footnote-line a:not(.reversefootnote) { color: inherit; }
.md-attr { display: none; }
.md-fn-count::after { content: "."; }
code, pre, tt { font-family: var(--monospace); }
.md-comment { color: rgb(162, 127, 3); opacity: 0.8; font-family: var(--monospace); }
code { text-align: left; }
a.md-print-anchor { border-width: initial !important; border-style: none !important; border-color: initial !important; display: inline-block !important; position: absolute !important; width: 1px !important; right: 0px !important; outline: 0px !important; background: 0px 0px !important; text-decoration: initial !important; text-shadow: initial !important; }
.md-inline-math .MathJax_SVG .noError { display: none !important; }
.mathjax-block .MathJax_SVG_Display { text-align: center; margin: 1em 0px; position: relative; min-width: 100%; width: auto; display: block !important; }
.MathJax_SVG_Display, .md-inline-math .MathJax_SVG_Display { width: auto; margin: inherit; display: inline-block !important; }
.MathJax_SVG .MJX-monospace { font-family: monospace; }
.MathJax_SVG .MJX-sans-serif { font-family: sans-serif; }
.MathJax_SVG { display: inline; font-style: normal; font-weight: 400; line-height: normal; zoom: 90%; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; min-width: 0px; border: 0px; padding: 0px; margin: 0px; }
.MathJax_SVG * { transition: none; }
.os-windows.monocolor-emoji .md-emoji { font-family: "Segoe UI Symbol", sans-serif; }
.md-diagram-panel > svg, [lang="flow"] svg, [lang="mermaid"] svg { max-width: 100%; }
[lang="mermaid"] .node text { font-size: 1rem; }
table tr th { border-bottom: 0px; }

.CodeMirror, .CodeMirror-sizer { position: relative; }
.CodeMirror.cm-s-inner { background: inherit; }
.fences-no-line-wrapping .md-fences .CodeMirror { margin-top: -30px; }
.CodeMirror-scroll { overflow-y: hidden; overflow-x: auto; }
.CodeMirror-lines { padding: 4px 0px; }
.CodeMirror-gutter-filler, .CodeMirror-scrollbar-filler { background-color: rgb(255, 255, 255); }
.CodeMirror-scroll, .cm-s-inner .CodeMirror-activeline-background { background: inherit; }
.CodeMirror-linenumber { padding: 0px 3px 0px 5px; text-align: right; color: rgb(153, 153, 153); }
.cm-s-inner .cm-keyword { color: rgb(119, 0, 136); }
.cm-s-inner .cm-atom, .cm-s-inner.cm-atom { color: rgb(34, 17, 153); }
.cm-s-inner .cm-number { color: rgb(17, 102, 68); }
.cm-s-inner .cm-def { color: rgb(0, 0, 255); }
.cm-s-inner .cm-variable { color: rgb(0, 0, 0); }
.cm-s-inner .cm-variable-2 { color: rgb(0, 85, 170); }
.cm-s-inner .cm-variable-3 { color: rgb(0, 136, 85); }
.cm-s-inner .cm-string { color: rgb(170, 17, 17); }
.cm-s-inner .cm-property { color: rgb(0, 0, 0); }
.cm-s-inner .cm-operator { color: rgb(152, 26, 26); }
.cm-s-inner .cm-comment, .cm-s-inner.cm-comment { color: rgb(170, 85, 0); }
.cm-s-inner .cm-string-2 { color: rgb(255, 85, 0); }
.cm-s-inner .cm-meta, .cm-s-inner .cm-qualifier { color: rgb(85, 85, 85); }
.cm-s-inner .cm-builtin { color: rgb(51, 0, 170); }
.cm-s-inner .cm-bracket { color: rgb(153, 153, 119); }
.cm-s-inner .cm-tag { color: rgb(17, 119, 0); }
.cm-s-inner .cm-attribute { color: rgb(0, 0, 204); }
.cm-s-inner .cm-header, .cm-s-inner.cm-header { color: rgb(0, 0, 255); }
.cm-s-inner .cm-quote, .cm-s-inner.cm-quote { color: rgb(0, 153, 0); }
.cm-s-inner .cm-hr, .cm-s-inner.cm-hr { color: rgb(153, 153, 153); }
.cm-s-inner .cm-link, .cm-s-inner.cm-link { color: rgb(0, 0, 204); }
.cm-negative { color: rgb(221, 68, 68); }
.cm-positive { color: rgb(34, 153, 34); }
.cm-header, .cm-strong { font-weight: 700; }
.cm-del { text-decoration: line-through; }
.cm-em { font-style: italic; }
.cm-link { text-decoration: underline; }
.cm-error, .cm-invalidchar { color: red; }
.cm-constant { color: rgb(38, 139, 210); }
.cm-defined { color: rgb(181, 137, 0); }
div.CodeMirror span.CodeMirror-matchingbracket { color: rgb(0, 255, 0); }
div.CodeMirror span.CodeMirror-nonmatchingbracket { color: rgb(255, 34, 34); }
.CodeMirror { height: auto; overflow: hidden; }
.CodeMirror-scroll { margin-bottom: -30px; padding-bottom: 30px; height: 100%; outline: 0px; position: relative; box-sizing: content-box; }
.CodeMirror-gutter-filler, .CodeMirror-hscrollbar, .CodeMirror-scrollbar-filler, .CodeMirror-vscrollbar { position: absolute; z-index: 6; display: none; }
.CodeMirror-vscrollbar { right: 0px; top: 0px; overflow-x: hidden; overflow-y: scroll; }
.CodeMirror-hscrollbar { bottom: 0px; left: 0px; overflow-y: hidden; overflow-x: scroll; }
.CodeMirror-scrollbar-filler { right: 0px; bottom: 0px; }
.CodeMirror-gutter-filler { left: 0px; bottom: 0px; }
.CodeMirror-gutters { border-right: 1px solid rgb(221, 221, 221); background: inherit; white-space: nowrap; position: absolute; left: 0px; top: 0px; padding-bottom: 30px; z-index: 3; }
.CodeMirror-gutter { white-space: normal; height: 100%; box-sizing: content-box; padding-bottom: 30px; margin-bottom: -32px; display: inline-block; }
.CodeMirror-gutter-wrapper { position: absolute; z-index: 4; background: 0px 0px !important; border: none !important; }
.CodeMirror-gutter-background { position: absolute; top: 0px; bottom: 0px; z-index: 4; }
.CodeMirror-gutter-elt { position: absolute; cursor: default; z-index: 4; }
.CodeMirror-lines { cursor: text; }
.CodeMirror pre { border-radius: 0px; border-width: 0px; background: 0px 0px; font-family: inherit; font-size: inherit; margin: 0px; white-space: pre; word-wrap: normal; color: inherit; z-index: 2; position: relative; overflow: visible; }
.CodeMirror-wrap pre { word-wrap: break-word; white-space: pre-wrap; word-break: normal; }
.CodeMirror-code pre { border-right: 30px solid transparent; width: fit-content; }
.CodeMirror-wrap .CodeMirror-code pre { border-right: none; width: auto; }
.CodeMirror-linebackground { position: absolute; left: 0px; right: 0px; top: 0px; bottom: 0px; z-index: 0; }
.CodeMirror-linewidget { position: relative; z-index: 2; overflow: auto; }
.CodeMirror-wrap .CodeMirror-scroll { overflow-x: hidden; }
.CodeMirror-measure { position: absolute; width: 100%; height: 0px; overflow: hidden; visibility: hidden; }
.CodeMirror-measure pre { position: static; }
.CodeMirror div.CodeMirror-cursor { position: absolute; border-right: none; width: 0px; visibility: hidden; }
.CodeMirror-focused div.CodeMirror-cursor { visibility: inherit; }
.CodeMirror-selected { background: rgb(217, 217, 217); }
.CodeMirror-focused .CodeMirror-selected { background: rgb(215, 212, 240); }
.cm-searching { background: rgba(255, 255, 0, 0.4); }
@media print {
.CodeMirror div.CodeMirror-cursor { visibility: hidden; }
}
.CodeMirror-lint-markers { width: 16px; }
.CodeMirror-lint-tooltip { background-color: infobackground; border: 1px solid rgb(0, 0, 0); border-radius: 4px; color: infotext; font-family: var(--monospace); overflow: hidden; padding: 2px 5px; position: fixed; white-space: pre-wrap; z-index: 10000; max-width: 600px; opacity: 0; transition: opacity 0.4s; font-size: 0.8em; }
.CodeMirror-lint-mark-error, .CodeMirror-lint-mark-warning { background-position: left bottom; background-repeat: repeat-x; }
.CodeMirror-lint-mark-error { background-image: url("data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAQAAAADCAYAAAC09K7GAAAAAXNSR0IArs4c6QAAAAZiS0dEAP8A/wD/oL2nkwAAAAlwSFlzAAALEwAACxMBAJqcGAAAAAd0SU1FB9sJDw4cOCW1/KIAAAAZdEVYdENvbW1lbnQAQ3JlYXRlZCB3aXRoIEdJTVBXgQ4XAAAAHElEQVQI12NggIL/DAz/GdA5/xkY/qPKMDAwAADLZwf5rvm+LQAAAABJRU5ErkJggg=="); }
.CodeMirror-lint-marker-error, .CodeMirror-lint-marker-warning { background-position: center center; background-repeat: no-repeat; cursor: pointer; display: inline-block; height: 16px; width: 16px; vertical-align: middle; position: relative; }
.CodeMirror-lint-message-error, .CodeMirror-lint-message-warning { padding-left: 18px; background-position: left top; background-repeat: no-repeat; }
.CodeMirror-lint-marker-error, .CodeMirror-lint-message-error { background-image: url("data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABAAAAAQCAMAAAAoLQ9TAAAAHlBMVEW7AAC7AACxAAC7AAC7AAAAAAC4AAC5AAD///+7AAAUdclpAAAABnRSTlMXnORSiwCK0ZKSAAAATUlEQVR42mWPOQ7AQAgDuQLx/z8csYRmPRIFIwRGnosRrpamvkKi0FTIiMASR3hhKW+hAN6/tIWhu9PDWiTGNEkTtIOucA5Oyr9ckPgAWm0GPBog6v4AAAAASUVORK5CYII="); }
.CodeMirror-lint-marker-warning, .CodeMirror-lint-message-warning { background-image: url("data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABAAAAAQCAMAAAAoLQ9TAAAANlBMVEX/uwDvrwD/uwD/uwD/uwD/uwD/uwD/uwD/uwD6twD/uwAAAADurwD2tQD7uAD+ugAAAAD/uwDhmeTRAAAADHRSTlMJ8mN1EYcbmiixgACm7WbuAAAAVklEQVR42n3PUQqAIBBFUU1LLc3u/jdbOJoW1P08DA9Gba8+YWJ6gNJoNYIBzAA2chBth5kLmG9YUoG0NHAUwFXwO9LuBQL1giCQb8gC9Oro2vp5rncCIY8L8uEx5ZkAAAAASUVORK5CYII="); }
.CodeMirror-lint-marker-multiple { background-image: url("data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAcAAAAHCAMAAADzjKfhAAAACVBMVEUAAAAAAAC/v7914kyHAAAAAXRSTlMAQObYZgAAACNJREFUeNo1ioEJAAAIwmz/H90iFFSGJgFMe3gaLZ0od+9/AQZ0ADosbYraAAAAAElFTkSuQmCC"); background-repeat: no-repeat; background-position: right bottom; width: 100%; height: 100%; }

:root { --side-bar-bg-color: #fafafa; --control-text-color: #777; }
@font-face { font-family: "Open Sans"; font-style: normal; font-weight: normal; src: local("Open Sans Regular"), url("./github/400.woff") format("woff"); }
@font-face { font-family: "Open Sans"; font-style: italic; font-weight: normal; src: local("Open Sans Italic"), url("./github/400i.woff") format("woff"); }
@font-face { font-family: "Open Sans"; font-style: normal; font-weight: bold; src: local("Open Sans Bold"), url("./github/700.woff") format("woff"); }
@font-face { font-family: "Open Sans"; font-style: italic; font-weight: bold; src: local("Open Sans Bold Italic"), url("./github/700i.woff") format("woff"); }
html { font-size: 16px; }
body { font-family: "Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif; color: rgb(51, 51, 51); line-height: 1.6; }
#write { max-width: 860px; margin: 0px auto; padding: 20px 30px 100px; }
#write > ul:first-child, #write > ol:first-child { margin-top: 30px; }
body > :first-child { margin-top: 0px !important; }
body > :last-child { margin-bottom: 0px !important; }
a { color: rgb(65, 131, 196); }
h1, h2, h3, h4, h5, h6 { position: relative; margin-top: 1rem; margin-bottom: 1rem; font-weight: bold; line-height: 1.4; cursor: text; }
h1:hover a.anchor, h2:hover a.anchor, h3:hover a.anchor, h4:hover a.anchor, h5:hover a.anchor, h6:hover a.anchor { text-decoration: none; }
h1 tt, h1 code { font-size: inherit; }
h2 tt, h2 code { font-size: inherit; }
h3 tt, h3 code { font-size: inherit; }
h4 tt, h4 code { font-size: inherit; }
h5 tt, h5 code { font-size: inherit; }
h6 tt, h6 code { font-size: inherit; }
h1 { padding-bottom: 0.3em; font-size: 2.25em; line-height: 1.2; border-bottom: 1px solid rgb(238, 238, 238); }
h2 { padding-bottom: 0.3em; font-size: 1.75em; line-height: 1.225; border-bottom: 1px solid rgb(238, 238, 238); }
h3 { font-size: 1.5em; line-height: 1.43; }
h4 { font-size: 1.25em; }
h5 { font-size: 1em; }
h6 { font-size: 1em; color: rgb(119, 119, 119); }
p, blockquote, ul, ol, dl, table { margin: 0.8em 0px; }
li > ol, li > ul { margin: 0px; }
hr { height: 4px; padding: 0px; margin: 16px 0px; background-color: rgb(231, 231, 231); border-width: 0px 0px 1px; border-style: none none solid; border-top-color: initial; border-right-color: initial; border-left-color: initial; border-image: initial; overflow: hidden; box-sizing: content-box; border-bottom-color: rgb(221, 221, 221); }
body > h2:first-child { margin-top: 0px; padding-top: 0px; }
body > h1:first-child { margin-top: 0px; padding-top: 0px; }
body > h1:first-child + h2 { margin-top: 0px; padding-top: 0px; }
body > h3:first-child, body > h4:first-child, body > h5:first-child, body > h6:first-child { margin-top: 0px; padding-top: 0px; }
a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 { margin-top: 0px; padding-top: 0px; }
h1 p, h2 p, h3 p, h4 p, h5 p, h6 p { margin-top: 0px; }
li p.first { display: inline-block; }
ul, ol { padding-left: 30px; }
ul:first-child, ol:first-child { margin-top: 0px; }
ul:last-child, ol:last-child { margin-bottom: 0px; }
blockquote { border-left: 4px solid rgb(221, 221, 221); padding: 0px 15px; color: rgb(119, 119, 119); }
blockquote blockquote { padding-right: 0px; }
table { padding: 0px; word-break: initial; }
table tr { border-top: 1px solid rgb(204, 204, 204); margin: 0px; padding: 0px; }
table tr:nth-child(2n) { background-color: rgb(248, 248, 248); }
table tr th { font-weight: bold; border-width: 1px 1px 0px; border-top-style: solid; border-right-style: solid; border-left-style: solid; border-top-color: rgb(204, 204, 204); border-right-color: rgb(204, 204, 204); border-left-color: rgb(204, 204, 204); border-image: initial; border-bottom-style: initial; border-bottom-color: initial; text-align: left; margin: 0px; padding: 6px 13px; }
table tr td { border: 1px solid rgb(204, 204, 204); text-align: left; margin: 0px; padding: 6px 13px; }
table tr th:first-child, table tr td:first-child { margin-top: 0px; }
table tr th:last-child, table tr td:last-child { margin-bottom: 0px; }
.CodeMirror-gutters { border-right: 1px solid rgb(221, 221, 221); }
.md-fences, code, tt { border: 1px solid rgb(221, 221, 221); background-color: rgb(248, 248, 248); border-radius: 3px; font-family: Consolas, "Liberation Mono", Courier, monospace; padding: 2px 4px 0px; font-size: 0.9em; }
.md-fences { margin-bottom: 15px; margin-top: 15px; padding: 8px 1em 6px; }
.md-task-list-item > input { margin-left: -1.3em; }
@media screen and (min-width: 914px)
@media print {
html { font-size: 13px; }
table, pre { break-inside: avoid; }
pre { word-wrap: break-word; }
}
.md-fences { background-color: rgb(248, 248, 248); }
#write pre.md-meta-block { padding: 1rem; font-size: 85%; line-height: 1.45; background-color: rgb(247, 247, 247); border: 0px; border-radius: 3px; color: rgb(119, 119, 119); margin-top: 0px !important; }
.mathjax-block > .code-tooltip { bottom: 0.375rem; }
#write > h3.md-focusbefore { left: -1.5625rem; top: 0.375rem; }
#write > h4.md-focusbefore { left: -1.5625rem; top: 0.285714rem; }
#write > h5.md-focusbefore { left: -1.5625rem; top: 0.285714rem; }
#write > h6.md-focusbefore { left: -1.5625rem; top: 0.285714rem; }
.md-image > .md-meta { border-radius: 3px; font-family: Consolas, "Liberation Mono", Courier, monospace; padding: 2px 0px 0px 4px; font-size: 0.9em; color: inherit; }
.md-tag { color: inherit; }
.md-toc { margin-top: 20px; padding-bottom: 20px; }
.sidebar-tabs { border-bottom: none; }
#typora-quick-open { border: 1px solid rgb(221, 221, 221); background-color: rgb(248, 248, 248); }
#typora-quick-open-item { background-color: rgb(250, 250, 250); border-color: rgb(254, 254, 254) rgb(229, 229, 229) rgb(229, 229, 229) rgb(238, 238, 238); border-style: solid; border-width: 1px; }
#md-notification::before { top: 10px; }
.on-focus-mode blockquote { border-left-color: rgba(85, 85, 85, 0.12); }
header, .context-menu, .megamenu-content, footer { font-family: "Segoe UI", Arial, sans-serif; }
.file-node-content:hover .file-node-icon, .file-node-content:hover .file-node-open-state { visibility: visible; }
.mac-seamless-mode #typora-sidebar { background-color: var(--side-bar-bg-color); }
.md-lang { color: rgb(180, 101, 77); }
.html-for-mac .context-menu { --item-hover-bg-color: #E6F0FE; }

.typora-export p {white-space: normal;}

结对编程项目报告--四则运算CORE

第15组：JL17110067 隆晋威 PB16120853 赵瑞

项目GitHub地址

https://github.com/NiceKingWei/homework2

PSP

status	stages	预估耗时	实际耗时
Accepted	make plan	20 min	20 min
Accepted	demand analysis	40 min	40 min
Accepted	analysis	45 min	90 min
Accepted	code	3 hours	5 hours
Accepted	test	2 hours	3 hours
Accepted	report	1 hours	2 hours
Sum		8 hours	12 hours

项目需求

像《构建之法》的人物阿超那样，写一个能自动生成小学四则运算题目并给出答案的命令行 “软件”，如果我们要把这个功能放到不同的环境中去（例如，命令行，Windows 图形界面程序，网页程序，手机App），就会碰到困难，因为目前代码的普遍问题是代码都散落在main ( )函数或者其他子函数中，我们很难把这些功能完整地剥离出来，作为一个独立的模块满足不同的需求。

API

setting() function:










x







1

void setting(



2

    int max_opearators,  //操作数的数目最大值



3

    long max_range,  //中间结果和结果的范围，如果是分数，只限制分母和最后结果的值



4

    int precision,   //精度



5

    int has_fraction,   //是否含有分数，1：含有，0：不含有分数



6

    int has_real)        //是否含有小数，1：含有，0：不含有1       



7

{   



8





9

    if (max_opearators != -1) global_setting.max_opearators = max_opearators;



10

    if (max_range != -1) global_setting.max_range = max_range;



11

    if (precision != -1) global_setting.precision = precision;



12

    if (has_fraction != -1) global_setting.has_fraction = has_fraction;



13

    if (has_real != -1) global_setting.has_real = has_real;



14

    global_setting.max_num = max_range / 10;



15

}

就是可以多次改变设置，在传入参数的时候，max_opearators、max_range、precision可以传入值或者-1，传值代表更改该设置，-1代表不变。has_fraction、has_real可以传入1，0，-1；1代表开启，0代表没有，-1代表不变。

generate函数：











xxxxxxxxxx

1









1

void generate(string* question, string* answer);

将参数传进去，运行后结果就存在了string* answer里面。

代码逻辑思路

我们首先定义了 fraction 类，这是分数类，用于符号计算。











xxxxxxxxxx

10









1

class fraction {



2

public:



3

    long numerator, denominator;



4

    void reduction() ;



5

    fraction operator + (const fraction x) const;



6

    fraction operator - (const fraction& x) const;



7

    fraction operator * (const fraction& x) const;



8

    fraction operator / (const fraction& x) const;



9

    fraction operator ^ (fraction x) const;



10

};

fraction 类里面重载了各个运算函数，并在每次计算结束之后通过类中的reduction()函数把分数变为最简分数。

然后定义了一些工具函数，如输出函数，判断是否是无效值的函数 is_bad_value











xxxxxxxxxx

2









1

bool is_bad_value(const fraction& x);



2

bool is_bad_value(const double& x);

is_bad_value 是一个判断值是否是坏值的函数。坏值在除零异常时可能会出现，在值超出范围的时候也会出现。坏值具有传递性，坏值和任何值运算的结果都是坏值。这种设计方式的灵感来自函数式语言中的 Maybe Monad ，下面放一下fraction operator / (const fraction x) const;作为例子：











xxxxxxxxxx

17









1

fraction operator / (const fraction& x) const {



2

        if (is_bad_value(*this))return *this;



3

        if (is_bad_value(x))return x;



4

        fraction stan_bad_value(1, 0);



5

        if (x.numerator == 0) {



6

            return stan_bad_value;



7

        }



8

        fraction result;



9

        result.numerator = this->numerator * x.denominator;



10

        result.denominator = this->denominator * x.numerator;



11

        result.reduction();



12

        if (is_bad_value(result)) {



13

            result.numerator = 1;



14

            result.denominator = 0;



15

        }



16

        return result;



17

    }

接下来定义抽象语法树的结构。











xxxxxxxxxx

30









1

enum ASTNodeType { TYPE_ADD = 0, TYPE_MINUS = 1, TYPE_MUL = 2, TYPE_DIV = 3, TYPE_POWER = 4, TYPE_FRACTION = 5, TYPE_DOUBLE = 6 };



2





3

struct ASTNode;



4





5

union NodeData {



6

    fraction frac;



7

    double real;



8

    pair<ASTNode*, ASTNode*> node;



9





10

    NodeData() {



11

        real = 0;



12

    }



13

};



14





15

struct ASTNode {



16

    ASTNodeType type;



17

    NodeData data;



18





19

    ASTNode() {



20

        type = TYPE_DOUBLE;



21

    }



22





23

    ~ASTNode() {



24

        if (type != TYPE_FRACTION && type != TYPE_DOUBLE) {



25

            delete data.node.first;



26

            delete data.node.second;



27

        }



28

    }



29

};



30

每一个抽象语法树的节点都包含两个字段，一个是 type，一个是 data。type 的类型是一个枚举值，data 是一个 union 联合体。这种做法的灵感也来自函数式语言。在表示抽象语法树时，tagged union 是一种很好的方式。但因为不确定能不能使用 c++17，所以我们并没有用类型安全的 std::variant ，而是使用了自己定义的tagged union。

之后的事情就比较简单了











xxxxxxxxxx

2









1

ASTNode* random_value(cal_mode mode); 



2

ASTNode* random_ast(cal_mode mode);

这两个函数产生随机值和随机抽象语法树，根据 setting 的规则产生合适的表达式树。

这两个函数的代码：











xxxxxxxxxx

64









1

inline ASTNode* random_value(cal_mode mode) {



2

    ASTNode* node = new ASTNode();



3

    int m, n;



4

    switch (mode) {



5

    case MODE_FRACTION:



6

        node->type = TYPE_FRACTION;



7

        m = rand() % (global_setting.max_num - 1) + 1;



8

        n = rand() % (m * 5);



9

        if (global_setting.has_fraction) {



10

            node->data.frac = fraction(n, m);



11

        }



12

        else {



13

            node->data.frac = fraction(m);



14

        }



15

        break;



16





17

    case MODE_REAL:



18

        node->type = TYPE_DOUBLE;



19

        double base = pow(10, global_setting.precision);



20

        node->data.real = floor((rand() / (double)RAND_MAX)*global_setting.max_num*base) / base;



21

        break;



22

    }



23

    return node;



24

}



25





26

ASTNode* random_ast(cal_mode mode) {



27

    int n = global_setting.max_opearators <= 1 ? 1 : rand() % (global_setting.max_opearators - 1) + 1;



28

    ASTNode* num1 = random_value(mode);



29

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



30

        ASTNode* num2 = random_value(mode);



31

        if (rand() % 2) swap(num1, num2);



32

        int r = rand() % 17;



33

        ASTNode* new_node = new ASTNode();



34





35





36

        if (r-- == 16 && (num2->type == TYPE_FRACTION || num2->type == TYPE_FRACTION) && (num1->type != TYPE_POWER) && global_setting.has_power) {



37

            if (mode == MODE_FRACTION) num2->data.frac = fraction(rand() % 4 + 1);



38

            else num2->data.real = rand() % 2 + 2;



39





40

            new_node->type = TYPE_POWER;



41

            new_node->data.node.first = num1;



42

            new_node->data.node.second = num2;



43

        }



44

        else {



45

            if (global_setting.has_mul_div) {



46

                new_node->type = (ASTNodeType)(r / 4);



47

                if (mode == MODE_FRACTION && !global_setting.has_fraction) {



48

                    r = rand() % 10;



49

                    if (r-- == 9) new_node->type = TYPE_DIV;



50

                    else new_node->type = (ASTNodeType)(r / 3);



51

                }



52

            }



53

            else {



54

                new_node->type = (ASTNodeType)(r / 8);



55

            }



56

            new_node->data.node.first = num1;



57

            new_node->data.node.second = num2;



58

        }



59





60

        num1 = new_node;



61

    }



62

    return num1;



63

}



64











xxxxxxxxxx

2









1

ASTNode* calc_asttree(ASTNode* root);



2

ASTNode* ast_eval(ASTNode* root);

calc_asttree 是递归函数，它递归调用自身，计算左子树和右子树的值，然后再计算当前节点的值，如果有一个结点的type是TYPE_DOUBLE，那么返回给上一层的type就是TYPE_DOUBLE。

这两个函数的代码











xxxxxxxxxx

166









1

long long hash_value;



2

ASTNode* calc_asttree(ASTNode* root) {



3

    ASTNode* result = new ASTNode();



4

    result->type = TYPE_FRACTION;



5

    result->data.frac;



6

    ASTNode* temp_a = new ASTNode();



7

    ASTNode* temp_b = new ASTNode();



8

    switch (root->type) {



9

    case TYPE_FRACTION:



10

        result->type = TYPE_FRACTION;



11

        result->data.frac = root->data.frac;



12

        break;



13

    case TYPE_DOUBLE:



14

        result->type = TYPE_DOUBLE;



15

        result->data.real = root->data.real;



16

        break;



17

    case TYPE_ADD:



18

        temp_a = calc_asttree(root->data.node.first);



19

        temp_b = calc_asttree(root->data.node.second);



20

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



21

            result->type = TYPE_FRACTION;



22

            result->data.frac = temp_a->data.frac + temp_b->data.frac;



23

        }



24

        else {



25

            result->type = TYPE_DOUBLE;



26

            double a, b;



27

            if (temp_a->type == TYPE_FRACTION) {



28

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



29

            }



30

            else if (temp_a->type == TYPE_DOUBLE) {



31

                a = temp_a->data.real;



32

            }



33

            if (temp_b->type == TYPE_FRACTION) {



34

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



35

            }



36

            else if (temp_b->type == TYPE_DOUBLE) {



37

                b = temp_b->data.real;



38

            }



39

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : (a + b);



40

        }



41

        break;



42

    case TYPE_MINUS:



43

        temp_a = calc_asttree(root->data.node.first);



44

        temp_b = calc_asttree(root->data.node.second);



45

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



46

            result->type = TYPE_FRACTION;



47

            result->data.frac = temp_a->data.frac - temp_b->data.frac;



48





49

        }



50

        else {



51

            result->type = TYPE_DOUBLE;



52

            double a, b;



53

            if (temp_a->type == TYPE_FRACTION) {



54

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



55

            }



56

            else if (temp_a->type == TYPE_DOUBLE) {



57

                a = temp_a->data.real;



58

            }



59

            if (temp_b->type == TYPE_FRACTION) {



60

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



61

            }



62

            else if (temp_b->type == TYPE_DOUBLE) {



63

                b = temp_b->data.real;



64

            }



65

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : (a - b);



66

        }



67

        break;



68

    case TYPE_MUL:



69

        temp_a = calc_asttree(root->data.node.first);



70

        temp_b = calc_asttree(root->data.node.second);



71

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



72

            result->type = TYPE_FRACTION;



73

            result->data.frac = temp_a->data.frac * temp_b->data.frac;



74





75

        }



76

        else {



77

            result->type = TYPE_DOUBLE;



78

            double a, b;



79

            if (temp_a->type == TYPE_FRACTION) {



80

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



81

            }



82

            else if (temp_a->type == TYPE_DOUBLE) {



83

                a = temp_a->data.real;



84

            }



85

            if (temp_b->type == TYPE_FRACTION) {



86

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



87

            }



88

            else if (temp_b->type == TYPE_DOUBLE) {



89

                b = temp_b->data.real;



90

            }



91

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : (a*b);



92

        }



93

        break;



94

    case TYPE_DIV:



95

        temp_a = calc_asttree(root->data.node.first);



96

        temp_b = calc_asttree(root->data.node.second);



97

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



98

            result->type = TYPE_FRACTION;



99

            result->data.frac = temp_a->data.frac / temp_b->data.frac;



100





101

        }



102

        else {



103

            result->type = TYPE_DOUBLE;



104

            double a, b;



105

            if (temp_a->type == TYPE_FRACTION) {



106

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



107

            }



108

            else if (temp_a->type == TYPE_DOUBLE) {



109

                a = temp_a->data.real;



110

            }



111

            if (temp_b->type == TYPE_FRACTION) {



112

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



113

            }



114

            else if (temp_b->type == TYPE_DOUBLE) {



115

                b = temp_b->data.real;



116

            }



117

            result->data.real = is_bad_value(a) || is_bad_value(b) || fabs(b) <= 1e-3 ? INFINITY : (a / b);



118

        }



119

        break;



120

    case TYPE_POWER:



121

        temp_a = calc_asttree(root->data.node.first);



122

        temp_b = calc_asttree(root->data.node.second);



123

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



124

            result->type = TYPE_FRACTION;



125

            result->data.frac = temp_a->data.frac ^ temp_b->data.frac;



126





127

        }



128

        else {



129

            result->type = TYPE_DOUBLE;



130

            double a, b;



131

            if (temp_a->type == TYPE_FRACTION) {



132

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



133

            }



134

            else if (temp_a->type == TYPE_DOUBLE) {



135

                a = temp_a->data.real;



136

            }



137

            if (temp_b->type == TYPE_FRACTION) {



138

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



139

            }



140

            else if (temp_b->type == TYPE_DOUBLE) {



141

                b = temp_b->data.real;



142

            }



143

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : powl(a, b);



144

        }



145

        break;



146

    }



147

    long long value = (long long)(root->type == TYPE_FRACTION ? (root->data.frac.numerator / (double)root->data.frac.denominator) : root->data.real);



148

    hash_value = (hash_value * 19260817 + value) % (long long)(1e9 + 7);



149

    delete temp_a;



150

    delete temp_b;



151

    if (result->type == TYPE_FRACTION) {



152

        if ( (result->data.frac.denominator > global_setting.max_range*100 || result->data.frac.numerator < 0) || 



153

             (result->data.frac.denominator != 1 && !global_setting.has_fraction)) {



154

            result->data.frac.numerator = 1;



155

            result->data.frac.denominator = 0;



156

        } 



157

    } else if (result->type == TYPE_DOUBLE && (result->data.real <0|| result->data.real>global_setting.max_range*10)) {



158

        result->data.real = INFINITY;



159

    }



160

    return result;



161

}



162





163

ASTNode* ast_eval(ASTNode* root) {



164

    hash_value = 0;



165

    return calc_asttree(root);



166

}

ast_eval 是调用 calc_asttree 的函数，它先把 hash_code 设为0，然后调用 calc_asttree

在calc_asttree 递归计算的过程中会产生一个操作序列，这个序列可以刻画当前表达式的特征，例如 1+2+3，在计算过程中产生的序列是 1+2=3, 3+3 =6，3+(2+1) 在计算过程中产生的序列为 2+1=3，3+3=6。若定义两个序列等价当前仅当序列中每个算式在交换律意义下等价。可以发现，题目要求的 “重复” 条件与计算序列的等价条件是等价的。因此，我们可以用计算序列来去重。

但计算序列的储存比较占空间，因此我们选择了一个哈希函数，对计算序列进行哈希映射。因为两个序列哈希值相同是两个序列重复的必要条件。因此在实际操作中，只需要两个序列哈希函数不同，则这两个表达式必然不相等。

接下来是表达式输出函数。











xxxxxxxxxx

13









1

/*



2

 * Expr := AddExpr | Expr + AddExpr



3

 * AddExpr := MulExpr | AddExpr * MulExpr



4

 * MulExpr := PowExpr | MulExpr ^ PowExpr



5

 * PowExpr := Number | (Expr)



6

 */



7

enum ExprType { EXPR_EXPR, EXPR_ADDEXPR, EXPR_MULEXPR, EXPR_POWEXPR };



8





9

void ast_output_expr(ASTNode* root, stringstream& ss);



10

void ast_output_addexpr(ASTNode* root, stringstream& ss);



11

void ast_output_mulexpr(ASTNode* root, stringstream& ss);



12

void ast_output_powexpr(ASTNode* root, stringstream& ss);



13

void ast_output_number(ASTNode* root, stringstream& ss);

注释中的内容是我们的计算表达式的 BNF 范式。由语法产生式，我们可以很容易地写出以上递归函数，并通过函数间的互相调用完成对表达式的输出，这种输出方式不会产生多余的括号。











xxxxxxxxxx

1









1

void generate(string* question, string* answer);

generate 函数生成题目和答案。它先调用 random_ast 生成一颗随机语法树，然后对它进行求值，如果结果是坏值，那就重新生成一个。

特别值得一提的是我们的 main 函数











xxxxxxxxxx

18









1

int main() {



2

    FILE* file = NULL;



3

    const long long test_num = 100000;



4

    const long long test_groups = 100;



5

    for (long long i = 0; i<test_num; i++) {



6

        if (i % (test_num / test_groups) == 0) {



7

            stringstream ss;



8

            ss << "test" << i / (test_num / test_groups) << ".py";



9

            if (file) fclose(file);



10

            file = fopen(ss.str().c_str(), "w");



11

        }



12

        string que, ans;



13

        generate(&que, &ans);



14

        fprintf(file, "assert(%lld>=0 and abs((%s)-(%s))<5e-2)\n", i, que.c_str(), ans.c_str());



15

    }



16

    fclose(file);



17

    return 0;



18

}

它为每一组数据生成了一行 python 代码，是一句断言。只要断言成立，这组数据就是正确的。只需要简单改改更改参数，我们就可以获得很多组数据，并能通过脚本进行自动测试。











xxxxxxxxxx

11









1

import os



2

import time



3

os.system("g++ core.cpp -O2 -g")



4

print("compile done.")



5

time.sleep(1);



6

os.system("./a.out")



7

time.sleep(1);



8

print("generate done.")



9

for i in range(0,100):



10

    os.system("pypy test%d.py" % i)



11

    print("test%d done." % i)

发布前，我们组一共测试了 500万组数据，均没有出错。

BUG记录

出现了错误的计算结果：

bug原因：我们俩搞错了乘方和乘法的运算优先级，
这个不太容易避免，出错了时候我们还疑问到底该先算乘方还是从左到右乘
大概四十分钟，找到错误样例，研究错误样例就可以了，发现了是逻辑错误，那么改代码就可以了。

第二次出现了错误的结果：

bug原因：分数运算的中间结果分子溢出了long long的范围
这个bug是在写函数时候错误的估计了可能用到的范围，没有加强函数的鲁棒性。
调试方法：用错误样例逐步测试，观察中间结果。
这种鲁棒性的东西，该加还是加上，尽量不要假设前提。

结对编程与个人作业差异

最初，隆晋威同学扮演驾驶员角色，赵瑞同学扮演领航员角色。

在完成整个程序的框架后，分工完成模块细节和测试，互相做驾驶员和领航员，在整个程序写完后，一起测试这个程序，并debug。

一个人用git很随意，可是两个人的话，就要提前看一下队友的修改。

个人看法

结对编程过程中，两个人的作息一致性很重要，在刚写完程序的时候，不出意外出了错误结果，我们开始debug，主要的debug任务是在凌晨完成的。debug到晚上十二点，1000组数据跑对了，后来加到10000又出错了，我们又debug到1点，10000没问题的时候，当时已经凌晨两点了，如果两个人有一个不习惯熬夜的话，这还真有点不舒服了，还好我俩都很不养生。

两个人的debug的速度果然不是1+1=2的简单加法，速度比一个人debug要快得多。

还有就是一起工作在有进展的时候两个人会一起觉得很开心，分享一下喜悦，比一个人有进展自己内心爽一下还happy，比如亮点debug完我们以为大功告成了就很开心（然而第二天加大测试量又出现了新的错误样例）。

结对编程过程中学习的速度时迅速的，这一次结对编程我向隆晋威同学学到了很多，比如代码规范，GitHub的使用和visual studio code的使用，还有用脚本来测试程序。

会选择结对编程用于解决部分任务。

工作时刻

结对编程项目报告--四则运算CORE

代码


















1

/*



2

* core.cpp



3

* author:



4

*   PB16120853 赵瑞



5

*   JL17110067 隆晋威



6

* date:



7

*  2018/4/5



8

*/



9

#define CORE15_API



10

#define TEST



11





12

#include <iostream>



13

#include <string>



14

#include <cstdio>



15

#include <tuple>



16

#include <cmath>



17

#include <sstream>



18

#include <set>



19





20

using namespace std;



21





22

/*



23

* global setting



24

*/



25

struct settings {



26

    int max_opearators = 5;



27

    long max_num = 100;         // max_range / 10



28

    long max_range = 1000;



29

    int precision = 2;



30

    bool has_fraction = true;



31

    bool has_real = true;



32

    bool has_mul_div = true;



33

    bool has_power = true;



34

};



35

settings global_setting;



36





37





38

/*



39

* fraction



40

*/



41

class fraction;



42

bool is_bad_value(const fraction& x);



43

bool is_bad_value(const double& x);



44





45





46





47

class fraction {



48

private:



49

    long gcd(long u, long v) {



50

        if (!(u&&v)) {



51

            return 1;



52

        }



53

        while (v != 0) {



54

            long r = u % v;



55

            u = v;



56

            v = r;



57

        }



58

        return u;



59

    }



60

public:



61

    long numerator, denominator;



62





63





64

    fraction(long m = 1, long n = 1) {



65

        this->numerator = m;



66

        this->denominator = n;



67

        this->reduction();



68

    }



69





70

    void reduction() {



71

        long x = gcd(this->numerator, this->denominator);



72

        if ((llabs(this->denominator) > global_setting.max_range) || (llabs(this->numerator) > global_setting.max_range)) {



73

            this->numerator = 1;



74

            this->denominator = 0;



75

            x = 1;



76

        }



77

        this->numerator /= x;



78

        this->denominator /= x;



79

        if (this->denominator < 0) {



80

            this->numerator *= -1;



81

            this->denominator *= -1;



82

        }



83

        if (!this->numerator) {



84

            this->denominator = 1;



85

        }



86

        if (!this->denominator) {



87

            this->numerator = 1;



88

        }



89

        if ((abs(this->denominator)>global_setting.max_range) || (abs(this->numerator) > global_setting.max_range)) {



90

            this->numerator = 1;



91

            this->denominator = 0;



92

        }



93

        return;



94

    }



95





96

    fraction operator + (const fraction x) const {



97

        if (is_bad_value(*this))return *this;



98

        if (is_bad_value(x))return x;



99

        fraction result;



100

        result.numerator = this->numerator * x.denominator + this->denominator * x.numerator;



101

        result.denominator = this->denominator * x.denominator;



102

        result.reduction();



103

        return result;



104

    }



105





106





107

    fraction operator - (const fraction& x) const {



108

        if (is_bad_value(*this))return *this;



109

        if (is_bad_value(x))return x;



110

        fraction result;



111

        result.numerator = this->numerator * x.denominator - this->denominator * x.numerator;



112

        result.denominator = this->denominator * x.denominator;



113

        result.reduction();



114

        return result;



115

    }



116





117

    fraction operator * (const fraction& x) const {



118

        if (is_bad_value(*this))return *this;



119

        if (is_bad_value(x))return x;



120

        fraction result;



121

        result.numerator = this->numerator * x.numerator;



122

        result.denominator = this->denominator * x.denominator;



123

        result.reduction();



124

        return result;



125

    }



126





127

    fraction operator / (const fraction& x) const {



128

        if (is_bad_value(*this))return *this;



129

        if (is_bad_value(x))return x;



130

        fraction stan_bad_value(1, 0);



131

        if (x.numerator == 0) {



132

            return stan_bad_value;



133

        }



134

        fraction result;



135

        result.numerator = this->numerator * x.denominator;



136

        result.denominator = this->denominator * x.numerator;



137

        result.reduction();



138

        if (is_bad_value(result)) {



139

            result.numerator = 1;



140

            result.denominator = 0;



141

        }



142

        return result;



143

    }



144





145

    fraction operator ^ (fraction x) const {



146

        if (is_bad_value(*this))return *this;



147

        if (is_bad_value(x))return x;



148





149

        x.reduction();



150

        if (x.denominator != 1) {



151

            fraction bad_value;



152

            bad_value.numerator = 1;



153

            bad_value.denominator = 0;



154

            return bad_value;



155

        }



156

        long index = x.numerator;



157





158

        fraction result;



159

        result.numerator = (long)powl(this->numerator, abs(index));



160

        result.denominator = (long)powl(this->denominator, abs(index));



161

        if (index < 0) {



162

            long temp;



163

            temp = result.numerator;



164

            result.numerator = result.denominator;



165

            result.denominator = temp;



166

        }



167

        result.reduction();



168

        return result;



169

    }



170

};



171





172

ostream& operator << (ostream& out, const fraction& frac) {



173

#ifdef DEBUG



174

    out << '(' << frac.numerator << ".0/" << frac.denominator << ".0)";



175

    return out;



176

#else



177

    long long n = frac.numerator;



178

    long long d = frac.denominator;



179

    long long integer = n / d;



180

    long long f = n % d;



181





182

    if (f == 0) {



183

        out << integer;



184

    }



185

    else {



186

        if (integer) {



187

            out << integer << '\'' << f << '/' << d;



188

        }



189

        else {



190

            out << f << '/' << d;



191

        }



192

    }



193

    return out;



194





195

#endif



196

}



197





198

/*



199

* unit test for fraction



200

*/



201

void fraction_test() {



202

    fraction a(1, 0), b(0, 1), c(2, 3), d(5, 6), e(8, 4), g(18, 9);



203

    fraction x;



204

    x = a + b;



205

    x = a * b;



206

    x = a - b;



207

    x = a / b;



208

    x = a / c;



209

    x = a + c;



210

    x = a * c;



211

    x = a - c;



212

    x = b + c;



213

    x = b - c;



214

    x = b * c;



215

    x = b / c;



216

    x = c * d;



217

    x = c / d;



218

    x = c + d;



219

    x = c - d;



220

    x = a ^ b;



221

    x = a ^ c;



222

    x = a ^ d;



223

    x = a ^ e;



224

    x = a ^ g;



225

    x = b ^ c;



226

    x = b ^ a;



227

    x = b ^ d;



228

    x = b ^ e;



229

    x = b ^ g;



230

    x = e * g;



231

    x = e - g;



232

    x = e + g;



233

    x = e / g;



234

}



235





236

/*



237

* is_bad_value



238

*/



239

bool is_bad_value(const fraction& x) {



240

    if (!x.denominator) {



241

        return true;



242

    }



243

    else {



244

        return false;



245

    }



246

}



247





248

bool is_bad_value(const double& x) {



249

    // todo: error



250

    if (isnan(x) || isinf(x)) {



251

        return true;



252

    }



253

    else {



254

        return false;



255

    }



256

}



257





258

/*



259

* AST



260

*/



261

enum ASTNodeType { TYPE_ADD = 0, TYPE_MINUS = 1, TYPE_MUL = 2, TYPE_DIV = 3, TYPE_POWER = 4, TYPE_FRACTION = 5, TYPE_DOUBLE = 6 };



262





263

struct ASTNode;



264





265

union NodeData {



266

    fraction frac;



267

    double real;



268

    pair<ASTNode*, ASTNode*> node;



269





270

    NodeData() {



271

        real = 0;



272

    }



273

};



274





275

struct ASTNode {



276

    ASTNodeType type;



277

    NodeData data;



278





279

    ASTNode() {



280

        type = TYPE_DOUBLE;



281

    }



282





283

    ~ASTNode() {



284

        if (type != TYPE_FRACTION && type != TYPE_DOUBLE) {



285

            delete data.node.first;



286

            delete data.node.second;



287

        }



288

    }



289

};



290





291





292





293

/*



294

* random ast



295

*/



296

enum cal_mode { MODE_FRACTION, MODE_REAL };



297





298

inline ASTNode* random_value(cal_mode mode) {



299

    ASTNode* node = new ASTNode();



300

    int m, n;



301

    switch (mode) {



302

    case MODE_FRACTION:



303

        node->type = TYPE_FRACTION;



304

        m = rand() % (global_setting.max_num - 1) + 1;



305

        n = rand() % (m * 5);



306

        if (global_setting.has_fraction) {



307

            node->data.frac = fraction(n, m);



308

        }



309

        else {



310

            node->data.frac = fraction(m);



311

        }



312

        break;



313





314

    case MODE_REAL:



315

        node->type = TYPE_DOUBLE;



316

        double base = pow(10, global_setting.precision);



317

        node->data.real = floor((rand() / (double)RAND_MAX)*global_setting.max_num*base) / base;



318

        break;



319

    }



320

    return node;



321

}



322





323

ASTNode* random_ast(cal_mode mode) {



324

    int n = global_setting.max_opearators <= 1 ? 1 : rand() % (global_setting.max_opearators - 1) + 1;



325

    ASTNode* num1 = random_value(mode);



326

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



327

        ASTNode* num2 = random_value(mode);



328

        if (rand() % 2) swap(num1, num2);



329

        int r = rand() % 17;



330

        ASTNode* new_node = new ASTNode();



331





332





333

        if (r-- == 16 && (num2->type == TYPE_FRACTION || num2->type == TYPE_FRACTION) && (num1->type != TYPE_POWER) && global_setting.has_power) {



334

            if (mode == MODE_FRACTION) num2->data.frac = fraction(rand() % 4 + 1);



335

            else num2->data.real = rand() % 2 + 2;



336





337

            new_node->type = TYPE_POWER;



338

            new_node->data.node.first = num1;



339

            new_node->data.node.second = num2;



340

        }



341

        else {



342

            if (global_setting.has_mul_div) {



343

                new_node->type = (ASTNodeType)(r / 4);



344

                if (mode == MODE_FRACTION && !global_setting.has_fraction) {



345

                    r = rand() % 10;



346

                    if (r-- == 9) new_node->type = TYPE_DIV;



347

                    else new_node->type = (ASTNodeType)(r / 3);



348

                }



349

            }



350

            else {



351

                new_node->type = (ASTNodeType)(r / 8);



352

            }



353

            new_node->data.node.first = num1;



354

            new_node->data.node.second = num2;



355

        }



356





357

        num1 = new_node;



358

    }



359

    return num1;



360

}



361





362





363

long long hash_value;



364

ASTNode* calc_asttree(ASTNode* root) {



365

    ASTNode* result = new ASTNode();



366

    result->type = TYPE_FRACTION;



367

    result->data.frac;



368

    ASTNode* temp_a = new ASTNode();



369

    ASTNode* temp_b = new ASTNode();



370

    switch (root->type) {



371

    case TYPE_FRACTION:



372

        result->type = TYPE_FRACTION;



373

        result->data.frac = root->data.frac;



374

        break;



375

    case TYPE_DOUBLE:



376

        result->type = TYPE_DOUBLE;



377

        result->data.real = root->data.real;



378

        break;



379

    case TYPE_ADD:



380

        temp_a = calc_asttree(root->data.node.first);



381

        temp_b = calc_asttree(root->data.node.second);



382

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



383

            result->type = TYPE_FRACTION;



384

            result->data.frac = temp_a->data.frac + temp_b->data.frac;



385

        }



386

        else {



387

            result->type = TYPE_DOUBLE;



388

            double a, b;



389

            if (temp_a->type == TYPE_FRACTION) {



390

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



391

            }



392

            else if (temp_a->type == TYPE_DOUBLE) {



393

                a = temp_a->data.real;



394

            }



395

            if (temp_b->type == TYPE_FRACTION) {



396

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



397

            }



398

            else if (temp_b->type == TYPE_DOUBLE) {



399

                b = temp_b->data.real;



400

            }



401

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : (a + b);



402

        }



403

        break;



404

    case TYPE_MINUS:



405

        temp_a = calc_asttree(root->data.node.first);



406

        temp_b = calc_asttree(root->data.node.second);



407

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



408

            result->type = TYPE_FRACTION;



409

            result->data.frac = temp_a->data.frac - temp_b->data.frac;



410





411

        }



412

        else {



413

            result->type = TYPE_DOUBLE;



414

            double a, b;



415

            if (temp_a->type == TYPE_FRACTION) {



416

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



417

            }



418

            else if (temp_a->type == TYPE_DOUBLE) {



419

                a = temp_a->data.real;



420

            }



421

            if (temp_b->type == TYPE_FRACTION) {



422

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



423

            }



424

            else if (temp_b->type == TYPE_DOUBLE) {



425

                b = temp_b->data.real;



426

            }



427

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : (a - b);



428

        }



429

        break;



430

    case TYPE_MUL:



431

        temp_a = calc_asttree(root->data.node.first);



432

        temp_b = calc_asttree(root->data.node.second);



433

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



434

            result->type = TYPE_FRACTION;



435

            result->data.frac = temp_a->data.frac * temp_b->data.frac;



436





437

        }



438

        else {



439

            result->type = TYPE_DOUBLE;



440

            double a, b;



441

            if (temp_a->type == TYPE_FRACTION) {



442

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



443

            }



444

            else if (temp_a->type == TYPE_DOUBLE) {



445

                a = temp_a->data.real;



446

            }



447

            if (temp_b->type == TYPE_FRACTION) {



448

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



449

            }



450

            else if (temp_b->type == TYPE_DOUBLE) {



451

                b = temp_b->data.real;



452

            }



453

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : (a*b);



454

        }



455

        break;



456

    case TYPE_DIV:



457

        temp_a = calc_asttree(root->data.node.first);



458

        temp_b = calc_asttree(root->data.node.second);



459

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



460

            result->type = TYPE_FRACTION;



461

            result->data.frac = temp_a->data.frac / temp_b->data.frac;



462





463

        }



464

        else {



465

            result->type = TYPE_DOUBLE;



466

            double a, b;



467

            if (temp_a->type == TYPE_FRACTION) {



468

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



469

            }



470

            else if (temp_a->type == TYPE_DOUBLE) {



471

                a = temp_a->data.real;



472

            }



473

            if (temp_b->type == TYPE_FRACTION) {



474

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



475

            }



476

            else if (temp_b->type == TYPE_DOUBLE) {



477

                b = temp_b->data.real;



478

            }



479

            result->data.real = is_bad_value(a) || is_bad_value(b) || fabs(b) <= 1e-3 ? INFINITY : (a / b);



480

        }



481

        break;



482

    case TYPE_POWER:



483

        temp_a = calc_asttree(root->data.node.first);



484

        temp_b = calc_asttree(root->data.node.second);



485

        if (temp_a->type == TYPE_FRACTION && temp_b->type == TYPE_FRACTION) {



486

            result->type = TYPE_FRACTION;



487

            result->data.frac = temp_a->data.frac ^ temp_b->data.frac;



488





489

        }



490

        else {



491

            result->type = TYPE_DOUBLE;



492

            double a, b;



493

            if (temp_a->type == TYPE_FRACTION) {



494

                a = (double)temp_a->data.frac.numerator / (double)temp_a->data.frac.denominator;



495

            }



496

            else if (temp_a->type == TYPE_DOUBLE) {



497

                a = temp_a->data.real;



498

            }



499

            if (temp_b->type == TYPE_FRACTION) {



500

                b = (double)temp_b->data.frac.numerator / (double)temp_b->data.frac.denominator;



501

            }



502

            else if (temp_b->type == TYPE_DOUBLE) {



503

                b = temp_b->data.real;



504

            }



505

            result->data.real = is_bad_value(a) || is_bad_value(b) ? INFINITY : powl(a, b);



506

        }



507

        break;



508

    }



509

    long long value = (long long)(root->type == TYPE_FRACTION ? (root->data.frac.numerator / (double)root->data.frac.denominator) : root->data.real);



510

    hash_value = (hash_value * 19260817 + value) % (long long)(1e9 + 7);



511

    delete temp_a;



512

    delete temp_b;



513

    if (result->type == TYPE_FRACTION) {



514

        if ( (result->data.frac.denominator > global_setting.max_range*100 || result->data.frac.numerator < 0) || 



515

             (result->data.frac.denominator != 1 && !global_setting.has_fraction)) {



516

            result->data.frac.numerator = 1;



517

            result->data.frac.denominator = 0;



518

        } 



519

    } else if (result->type == TYPE_DOUBLE && (result->data.real <0|| result->data.real>global_setting.max_range*10)) {



520

        result->data.real = INFINITY;



521

    }



522

    return result;



523

}



524





525

ASTNode* ast_eval(ASTNode* root) {



526

    hash_value = 0;



527

    return calc_asttree(root);



528

}



529





530

/*



531

* Expr := AddExpr | Expr + AddExpr



532

* AddExpr := MulExpr | AddExpr * MulExpr



533

* MulExpr := PowExpr | MulExpr ^ PowExpr



534

* PowExpr := Number | (Expr)



535

*/



536

enum ExprType { EXPR_EXPR, EXPR_ADDEXPR, EXPR_MULEXPR, EXPR_POWEXPR };



537





538

void ast_output_expr(ASTNode* root, stringstream& ss);



539

void ast_output_addexpr(ASTNode* root, stringstream& ss);



540

void ast_output_mulexpr(ASTNode* root, stringstream& ss);



541

void ast_output_powexpr(ASTNode* root, stringstream& ss);



542

void ast_output_number(ASTNode* root, stringstream& ss);



543





544

void ast_output_expr(ASTNode* root, stringstream& ss) {



545

    switch (root->type) {



546

    case TYPE_ADD:case TYPE_MINUS:



547

        ast_output_expr(root->data.node.first, ss);



548

        ss << (root->type == TYPE_ADD ? " + " : " - ");



549

        ast_output_addexpr(root->data.node.second, ss);



550

        break;



551





552

    default:



553

        ast_output_addexpr(root, ss);



554

        break;



555

    }



556

}



557





558

void ast_output_addexpr(ASTNode* root, stringstream& ss) {



559

    switch (root->type) {



560

    case TYPE_MUL:case TYPE_DIV:



561

        ast_output_addexpr(root->data.node.first, ss);



562

        ss << (root->type == TYPE_MUL ? " * " : " / ");



563

        ast_output_mulexpr(root->data.node.second, ss);



564

        break;



565





566

    default:



567

        ast_output_mulexpr(root, ss);



568

        break;



569

    }



570

}



571





572

void ast_output_mulexpr(ASTNode* root, stringstream& ss) {



573

    switch (root->type) {



574

    case TYPE_POWER:



575

        ast_output_mulexpr(root->data.node.first, ss);



576

#ifdef DEBUG



577

        ss << " ** ";



578

#elif defined(TEST)



579

        ss << " ** ";



580

#else       



581

        ss << "^";



582

#endif



583

        ast_output_powexpr(root->data.node.second, ss);



584

        break;



585

    default:



586

        ast_output_powexpr(root, ss);



587

        break;



588

    }



589

}



590





591

void ast_output_powexpr(ASTNode* root, stringstream& ss) {



592

    switch (root->type) {



593

    case TYPE_FRACTION:



594

        ss << root->data.frac;



595

        break;



596

    case TYPE_DOUBLE:



597

        ss << root->data.real;



598

        break;



599

    default:



600

        ss << '(';



601

        ast_output_expr(root, ss);



602

        ss << ')';



603

        break;



604

    }



605

}



606





607

set<long long> ans_set;



608





609

CORE15_API void set_setting(



610

    int max_opearators,



611

    long max_range,



612

    int precision,



613

    int has_fraction,



614

    int has_real,



615

    int has_mul_div,



616

    int has_power) {



617





618

    if (max_opearators != -1) global_setting.max_opearators = max_opearators;



619

    if (max_range != -1) global_setting.max_range = max_range;



620

    if (precision != -1) global_setting.precision = precision;



621

    if (has_fraction != -1) global_setting.has_fraction = has_fraction != 0;



622

    if (has_real != -1) global_setting.has_real = has_real != 0;



623

    if (has_mul_div != -1) global_setting.has_mul_div = has_mul_div != 0;



624

    if (has_power != -1) global_setting.has_power = has_power != 0;



625

    global_setting.max_num = max_range>=20 ? max_range / 10 : max_range;



626

}



627





628

#ifdef TEST



629

int c1=0,c2=0;



630

#endif



631

CORE15_API void generate(string* question, string* answer) {



632

    cal_mode mode;



633

    int magic = global_setting.has_fraction ? 32 : 3;



634

    if (global_setting.has_real && rand() % magic == 0) {



635

        mode = MODE_REAL;



636

    } else{



637

        mode = MODE_FRACTION;



638

    }



639

    question->clear();



640

    answer->clear();



641





642

    ASTNode* node = random_ast(mode);



643

    ASTNode* ret = ast_eval(node);



644

    bool bad_value = false;



645





646

    stringstream s1, s2;



647

    s1.setf(std::ios::fixed, std::ios::floatfield);



648

    s2.setf(std::ios::fixed, std::ios::floatfield);



649





650

    s2.precision(global_setting.precision);



651

    if (ret->type == TYPE_DOUBLE && !is_bad_value(ret->data.real)) {



652

        s2 << ret->data.real;



653

    }



654

    else if (ret->type == TYPE_FRACTION && !is_bad_value(ret->data.frac)) {



655

#ifdef DEBUG



656

        s2 << (ret->data.frac.numerator / (double)ret->data.frac.denominator);



657

#else



658

        s2 << ret->data.frac;



659

#endif



660

    }



661

    else {



662

        bad_value = true;



663

    }



664

    *answer = s2.str();



665





666

    if (bad_value || ans_set.find(hash_value) != ans_set.end()) {



667

        generate(question, answer);



668

        delete node;



669

        delete ret;



670

        return;



671

    }



672

    else {



673

        ans_set.insert(hash_value);



674

    }



675





676

    s1.precision(global_setting.precision);



677

    ast_output_expr(node, s1);



678

    *question = s1.str();



679





680

    delete node;



681

    delete ret;



682





683

#ifdef TEST



684

    if(mode==MODE_FRACTION) c1++;



685

    else c2++;



686

#endif



687





688

    return;



689

}



690





691





692

#ifdef DEBUG



693

// for unit test



694

int main() {



695

    // todo: random



696

    FILE* file = NULL;



697

    const long long test_num = 100000;



698

    const long long test_groups = 100;



699

    for (long long i = 0; i<test_num; i++) {



700

        if (i % (test_num / test_groups) == 0) {



701

            stringstream ss;



702

            ss << "test" << i / (test_num / test_groups) << ".py";



703

            if (file) fclose(file);



704

            file = fopen(ss.str().c_str(), "w");



705

        }



706

        string que, ans;



707

        generate(&que, &ans);



708

        fprintf(file, "assert(%lld>=0 and abs((%s)-(%s))<5e-2)\n", i, que.c_str(), ans.c_str());



709

    }



710

    fclose(file);



711

    return 0;



712

}



713

#elif defined(TEST)



714

int main() {



715

    srand(time(NULL));



716

    for (long long i = 0; i<200; i++) {



717

        string que, ans;



718

        generate(&que, &ans);



719

        cout << que << " = " << ans << endl;



720

    }



721

    cout<<c1<<" "<<c2<<endl;



722

    return 0;



723

}



724

#endif

秒客网

结对编程项目报告--四则运算CORE

结对编程项目报告--四则运算CORE

项目GitHub地址

PSP

项目需求

API

代码逻辑思路

BUG记录

结对编程与个人作业差异

个人看法

工作时刻

代码

相关文章