Chord Segmentation and Recognition using EM-Trained Hidden Markov Models
Chord Segmentation and Recognition using EM-Trained Hidden Markov Models
Alexander Sheh and Daniel P.W.Ellis
LabROSA,Dept.of Electrical Engineering,
Columbia University,New York NY10027USA
{asheh79,dpwe}@https://www.wendangku.net/doc/5c17706002.html,
Abstract
Automatic extraction of content description from
commercial audio recordings has a number of impor-
tant applications,from indexing and retrieval through
to novel musicological analyses based on very large
corpora of recorded performances.Chord sequences
are a description that captures much of the charac-
ter of a piece in a compact form and using a mod-
est lexicon.Chords also have the attractive property
that a piece of music can(mostly)be segmented into
time intervals that consist of a single chord,much as
recorded speech can(mostly)be segmented into time
intervals that correspond to speci?c words.In this
work,we build a system for automatic chord tran-
scription using speech recognition tools.For features
we use“pitch class pro?le”vectors to emphasize the
tonal content of the signal,and we show that these
features far outperform cepstral coef?cients for our
task.Sequence recognition is accomplished with hid-
den Markov models(HMMs)directly analogous to
subword models in a speech recognizer,and trained
by the same Expectation-Maximization(EM)algo-
rithm.Crucially,this allows us to use as input only
the chord sequences for our training examples,with-
out requiring the precise timings of the chord changes
—which are determined automatically during train-
ing.Our results on a small set of20early Beatles
songs show frame-level accuracy of around75%on a
forced-alignment task.
Keywords:audio,music,chords,HMM,EM.
1Introduction
The human auditory system is capable of extracting rich and meaningful data from complex audio signals.Machine listening research attempts to model this process using computers.In the music domain,there has been limited success when the input signal or analysis is relatively simple,i.e.single instrument, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advan-tage and that copies bear this notice and the full citation on the?rst page.c 2003Johns Hopkins University.beat detection,etc.Unfortunately,for complex signals,such as ensemble performances,or more complex analyses,such as pitch transcription,the task rapidly increases in dif?culty.In this paper we investigate a problem with complexity in both dimensions,chord recognition on unstructured,polyphonic,and multi-timbre audio.A system able to transcribe an arbitrary audio recording into an accurate chord sequence would have many applications in?nding particular examples or themes in large audio databases,as well as enabling interesting new large-scale statistical analyses of musical content.
Our speci?c approach uses the hidden Markov models(HMMs) made popular in speech recognition(Gold and Morgan,1999), including the sophisticated Expectation-Maximization(EM)al-gorithm used to train them.This is a statistical approach,in which the wide variety of feature frames falling under a sin-gle label is modeled as random variation that follows an esti-mated distribution.By making a direct analogy between the sequence of discrete,non-overlapping chord symbols used to describe a piece of music,and the word sequence used to de-scribe recorded speech,much of the speech recognition frame-work can be used with minimal modi?cation.In particular,no timing alignment is required between the chord labels and the training audio—using the constraints of the chord sequence alone,the EM approach converges to?nd optimal segmenta-tions.
We draw on the prior work of Fujishima(1999)who proposed a representation of audio termed“pitch class pro?les”(PCPs),in which the Fourier transform intensities are mapped to the twelve semitone pitch classes(chroma).This is very similar to the “chroma spectrum”proposed by Bartsch and Wake?eld(2001). The assumption is that this representation captures harmonic in-formation in a more meaningful way,thereby facilitating chord recognition.Fujishima’s system uses nearest-neighbor classi?-cation to chord templates,and performed well on samples con-taining a single instrument.
Our system has parallels with the work by Raphael(2002),who also uses HMMs trained by EM to transcribe music in terms of chord labels.However,since his ultimate goal is note-level tran-scription,his“chord”vocabulary distinguishes between each different combination of simultaneous notes,in contrast to our approach of having a single model for“A minor”etc.This huge state space precludes direct training of models for each chord, and instead structural information about the harmonics expected for any given note combination are used to select among a rel-atively small set of model‘factors’,from which the desired
chord models may be assembled.His system is applied to clean recordings of solo piano music.
In section2,we describe the structure of our chord analysis sys-tem in detail.Section3describes the experiments we conducted to evaluate the system,by training and testing on a small collec-tion of20early Beatles songs.Finally,section4discusses our future work followed by our conclusions.
2System
The chord recognition system is presented below.
First the input signal is transformed to the frequency domain. Then it is mapped to the PCP domain by summing and normal-izing the pitch chroma intensities,for every time slice.These features are then used to build chord models via EM.Finally, chord alignment/recognition is performed with the Viterbi al-gorithm.
2.1Pitch Class Pro?le Features
Monophonic music recordings x[n]sampled at11025Hz are divided into overlapping frames of N=4096points and con-verted to a short-time Fourier transform(STFT)representation,
X ST F T[k,n]=N?1
m=0
x[n?m]·w[m]·e?j2πkm/N(1)
where k indexes the frequency axis with0≤k≤N?1,n is the short-time window center,and w[m]is an N-point Hanning window.The STFT is then mapped to the Pitch Class Pro?le (PCP)features,which traditionally consist of12-dimensional vectors,with each dimension corresponding to the intensity of a semitone class(chroma).The procedure collapses pure tones of the same pitch class,independent of octave,to the same PCP bin;for complex tones,the harmonics also fall into particular, related bins.Frequency to pitch mapping is achieved using the logarithmic characteristic of the equal temperament scale.Our experiments use a?ner grained PCP vector of24dimensions to give some?exibility in accounting for slight variations in tuning.A step size of100ms,or10PCP frames per second,is employed.STFT bins k are mapped to PCP bins p according to:
p(k)= 24.log2(k/N.f sr/f ref) mod24(2) where f ref is the reference frequency corresponding to P CP[0] and f sr is the sampling rate.For each time slice,we calculate the value of each PCP element by summing the magnitude of all frequency bins that correspond to a particular pitch class i.e. for p=0,1, (23)
P CP[p]=
k:p(k)=p
|X[k]|2(3)
2.2Hidden Markov Models
PCP vectors are used as features to train a hidden Markov model (HMM)with one state for each chord distinguished by the sys-tem.An HMM is a stochastic?nite automaton in which each state generates an observation.The state transitions obey the Markovian property,that given the present state,the future is independent of the past.(For an introduction to HMMs,see Gold and Morgan(1999)).To model the PCP vector distribution for each state,we assume a single Gaussian in24dimensions,described by its mean vec-torμi and covariance metricΣi We additionally assume that the features are uncorrelated with each other,so thatΣi con-sists only of variances,i.e.all off-diagonal elements are zero. To specify the model we need to determine the24dimension mean vectorμi and the24dimension variance vector diag(Σi) associated with the emitting state,and the transition probabili-ties.
If we knew which state(i.e.chord)generated each observa-tion in our training data,the model parameters could be directly estimated.Hand-marked chord boundaries could provide the necessary information,but it is extremely time-consuming to create these?les.In our case,we assume only that the chord sequence of an entire piece is known,but treat the chord labels of each frame as hidden values within the EM framework.This frees the researcher from the laborious and problematic process of manual annotation.
2.3Expectation Maximization
The expectation maximization(EM)algorithm(Gold and Mor-gan,1999)is an approach that structures the statistical classi-?er parameter estimation problem to incorporate hidden vari-ables.We assume a joint density between the observed and missing(hidden)variables,de?ning the complete-data likeli-hood P(X,Q|Θ)where X represents the observed feature vec-tors,Q stands for the unknown chord labels,andΘholds the current model parameters.EM estimates the densities by taking an expectation of the logarithm of the complete-data likelihood, E[logP(X,Q|Θ)]=
Q
P(Q|x,Θold)log(P(X|Q,Θ)P(Q|Θ)
(4) This equation expresses the complete-data log likelihood as a function of old and new parameters,Θold andΘ.At each step the old parameters are?xed,andΘis adjusted to maximize logP(X,Q|Θ)in expectation.This process is iterated until the expected improvement is no larger than some .EM guarantees that the estimates will improve at each step,resulting in a locally optimal set of parameters,though not necessarily the globally optimal solution.Thus,the EM solution reasonably estimates a set of parameters that maximizes the complete-data likelihood, which implements the original MAP decision rule.
The speci?c application of EM to?nd maximum-likelihood parameter estimates for a hidden Markov model is known as the Baum-Welch,or forward-backward algorithm.The up-date equations derived from maximizing equation4amount to setting model parameters to the sample averages of the train-ing features,weighted by the posterior probability of each feature being associated with each particular hidden label, p(q i n|X,Θold,M),where M is the model comprising the con-straints on observations X,constructed by concatenating the states speci?ed in the known chord sequence into a single com-posite HMM for each song.
2.4Viterbi Alignment
The EM algorithm calculates the mean and variance vector val-ues,and the transition probabilities for each chord HMM.With these parameters de?ned,the model can now be used to de-termine a chord labeling for each song.The Viterbi algorithm (Gold and Morgan,1999)is used to either forcibly align or
Input Signal
G#
G
F#
F
E
D#
D
C#
C
B
A#
A
normalized
DFT frames
PCP frames
Transcription / Alignment 0
11kHz
Chord Models C C C AmAm
Am
C
.
.
.
.
.
.
.
Figure1:System Overview recognize these labels;in forced alignment,observations are
aligned to a composed HMM whose transitions are limited to
those dictated by a speci?c chord sequence,as in training i.e.
only the chord-change times are being recovered,since the
chord sequence is known.In recognition,the HMM is uncon-
strained,in that any chord may follow any other,subject only to
the Markov constraints in the trained transition matrix.We per-
form both sets of experiments to demonstrate that even when
pure recognition performance is quite poor,a reasonable ac-
curacy under forced alignments indicates that the models have
succeeded in learning the desired chord characteristics to some
extent.The output of the Viterbi algorithm is the single state-
path labeling with the highest likelihood given the model pa-
rameters.This best-path assigns a chord to every100ms time
slice,resulting in a time-aligned song transcription.
2.5Weighted Averaging of Rotated PCP Vectors
The outcome of the EM training is a set of model parameters
including means and variances in PCP feature space for each of
the de?ned chord states.These values de?ne our initial chord
models,however,an improvement can be made by calculating a
weighted average of the models for every chord family(major,
minor,maj7etc.)across all root chromas(A,A#,B,C,etc.).
This involves rotating the PCP vectors from each chroma until
PCP[0]is the root pitch class,computing a weighted average
across all the chromas(weighted by frequency of chord occur-
rence),then un-rotating the weighted average PCP vectors back
to their original positions to construct new,regularized models
for each chord.Thus,if f indexes across chord families and c
is the numerical offset of each chroma relative to A in quarter
tones(e.g.A→0,A#→2,B→4etc.),then the mean vector
for the parent model of chord family f in PCP space is
ˉμf[p]=
c
μf,c[(p?c)mod24]·N f,c
c
N f,c
(5)
whereμf,c is the original mean vector for one speci?c chord family/chroma combination,N f,c is the number of frames as-signed to that state in forced alignment of the training data,and p indexes the24PCP bins.The rotated models then replace the individual family/chroma state models with
ˉ
μf,c[p]=ˉμf[(p+c)mod24](6) (Variances are similarly pooled).The motivation is that by using values characteristic to the entire family,a derived state model avoids over?tting its particular chord data.There is also the advantage of increasing each individual chord’s training set to
Album Song Set
Beatles for Sale Eight days a week test
Every little thing test
I don’t want to spoil
the party
train
I’ll follow the sun train
I’m a loser train Help Help train
I’ve just seen a face train
It’s only love train
Ticket to ride train
Yesterday train
You’re going to lose
that girl
train
You’ve got to hide
your love away
train
A Hard Day’s Night A hard day’s night train
And I love her train
Can’t buy me love train
I should’ve known
better
train
I’m happy just to
dance with you
train
If I fell train
Tell me why train
Things we said today train Table1:Corpus of20early Beatles songs used in the experi-ments.
the union of all chord family members.The results below show that this simple approach gave very signi?cant improvements.
3Implementation and Experiments
The Hidden Markov Model Toolkit(Young et al.,1997)was used to implement our chord recognition system.Twenty songs from three early Beatles albums were selected for our experi-ments(see table1).The songs were read from CD then down-sampled and mixed into mono?les at11025Hz sampling rate. The chord sequences for each song were produced by mapping the progressions from a standard book of Beatles transcriptions (Paperback Song Series:The Beatles,1995)to a simpler set of chords as shown in table2.The twenty sound?les and their as-sociated chord sequences comprise the input to our system.Two songs,“Eight Days a Week”and“Every Little Thing”,were
Chord families maj,min,maj7,min7,
dom7,aug,dim
Roots A ,B ,C ,D ,E ,F ,G ,
A,B,C,D,E,F,G,
A ,
B ,
C ,
D ,
E ,
F ,
G ,
Examples Amaj,C min7,G dom7
Table2:De?nition of the147possible chords that can appear as HMM states.The label“X”is given to chords not covered by this set.In practice,only32labels occurred in our data.
Feature Align Recog
train18train20train18train20 MFCC27.020.9 5.916.7
14.523.07.719.6
MFCC D24.113.115.87.6
19.919.7 1.5 6.9
MFCC0D A13.911.0 2.2 3.8
9.212.3 1.3 2.5
PCP26.341.010.023.6
46.253.718.226.4
PCP ROT68.868.323.323.1
83.383.820.113.1 Table3:Percent Frame Accuracy results.Within each row,the ?rst subrow refers to“Eight Days a Week”and second subrow to“Every Little Thing”.Columns show the frame accuracy for forced alignment and recognition,using the train18(excluding test cases)and train20(including test cases)sets. designated as the test set,and for these songs the actual chord boundaries were hand-labeled using WaveSurfer;this provided the ground-truth used to determine frame error rates.
We made separate HMM trainings using?ve distinct feature con?gurations.The?rst three use Mel-frequency cepstral co-ef?cients(MFCCs),the ubiquitous features of speech recogni-tion,calculated using HTK We included MFCCs as a compari-son:We did not expect them to be well suited to this task,since these features suppress pitch information.However,MFCCs have performed surprisingly well in some other music content analysis tasks(Logan,2000),so they make a good baseline.In each case,the total model dimensions were kept at24to match the number of parameters in the PCP systems;in the?rst case (MFCC)we used24MFCCs to get a relatively?ne spectral description.Case2(MFCC D)used just12MFCCs but in-cluded their deltas(velocities)since these are a popular addi-tion in speech recognition.The third case(MFCC0D A)used 7th order MFCCs including the c0(average log energy)term, along with deltas and accelerations for each dimension,again mimicking successful speech feature con?gurations.
The remaining two feature con?gurations are plain PCP vectors (PCP)and the averaged PCP vector rotations(PCP ROT),both in24dimensions.A matlab script was written to perform a STFT of Hanning length4096,and a subsequent PCP mapping using reference frequency440Hz(A4).
We trained on the18songs from our dataset not designated as test examples.We also repeated the experiments training on all 20songs—i.e.including the test examples—to establish a performance ceiling in the optimistic condition when the test
Figure3:Mean vectors for the PCP ROT average chord family templates.
cases exactly match part of the training set.
Training begins with the uniform segmentation and chord label-ing of every training song,using chord sequence information. HMM state chord models were initialized with global mean and variance values from the entire dataset(so called?at-start EM initialization).Ideally,enough of the chord models align with the actual realizations of the chord to allow successively more accurate models to evolve during training iterations.Prior to training,a single composite HMM for each song is constructed according to the chord sequence information(see section2.2), which constrains the training process.EM proceeds for13to15 iterations.After all the training songs have been processed,the total set of statistics is used to re-estimate the parameters of the individual chord models.At this point,averaged-rotated PCP models are combined as described in section2.5.
Lastly,the Viterbi algorithm is applied to generate either a boundary alignment of an existing chord sequence or recog-nize a new chord sequence.In the case of alignment,the chord sequence?le is used to generate a simple composite HMM with allowable transitions determined by the song’s progres-sion.Recognition must be able to accommodate any sequence drawn from the set of training song chords.An appropriate chord loop is derived from the chord sequence?les of all train-ing songs.The Viterbi algorithm will determine the best path in this chord network.Each PCP frame is assigned a chord class such that the likelihood of the entire path is maximized.The chord-labeled frame sequence along this path is the aligned or recognized output of the system.By comparing the automatic chord labels with the hand-marked ground-truth labels of the test examples,we can calculate the frame error rate.
3.1Frame Accuracy Results
A summary of the frame accuracy results is presented in ta-ble3,with the alignment and recognition accuracy percentages on each of the two test examples for the?ve feature con?gura-tions and two training sets.We see that models trained using the base PCP features perform better than models trained us-ing MFCCs in all cases except one(recognition of the?rst test example using MFCC D and train18).Using averaged-rotated PCPs(PCP ROT)results in models that outperform all MFCC-trained ones,as well as the base PCP models in all cases ex-
true E G D Bm
G
align E G DBm G recog
E
G
Bm
Am
Em7Bm
Em7
16.27
24.84time / sec
intensity
A #
B
C #
D #
E F
#G #p i t c h c l a s s Beatles - Beatles For Sale - Eight Days a Week (4096pt)
200406080100
120
Figure 2:Illustration of PCP features vectors,ground truth labels,forced alignment output,and recognition output,for a brief segment of “Eight Days a Week”.
cept,curiously,recognition based on train20.The strength of the PCP representation,and the model averaging approach,is clearly demonstrated,with the PCP ROT models performing as much a four times better than the best MFCC counterparts.Forced alignment always outperforms recognition,as expected since the basic chord sequence is already known in forced align-ment which then has only to determine the boundaries,whereas recognition has to determine the chord labels https://www.wendangku.net/doc/5c17706002.html,paring the performance of train18and train20(i.e.testing on examples that are distinct from,or included in,the training set),we see a mixed effect with MFCC features.For the PCP system,testing on the training set (train20)gives a signi?cant increase in ac-curacy for both alignment and recognition,indicating that these models are able to exploit the ‘cheating’information of getting a preview of the test cases.By contrast,PCP ROT achieves no bene?t from training on the test set (and even does signi?-cantly worse on recognizing “Every Little Thing”,which may re?ect some pathological case in the local maximum found by EM).As a general rule,if including the test data in the training set does not signi?cantly increase performance,we can at least be con?dent that the models are not over?tting the data;thus,for PCP ROT,we could try training with more model param-eters,such as Gaussian mixtures rather than single Gaussians,since we have not already over?t our models to the data—even though this is already the best-performing system overall.3.2Chord Confusion
Greater insight into system performance can be obtained by ex-amining the speci?c kinds of errors being made in terms of mis-recognitions of particular chords into other classes.The case we are most interested in is recognition (rather than alignment)us-
ing weight-averaged PCP HMMs (PCP ROT),trained without using test songs (train18).Table 4presents the confusion ma-trices for every frame in “Eight Days a Week”,which we label with only 5chords plus “X”.Notice the frequent confusion be-tween major chords and their minor version,which differ only by the semitone between the major and minor third intervals.Better discrimination of these chords might be achieved by in-creasing the system’s frequency resolution.3.3Model Means
Figure 3shows the actual PCP-domain ‘signatures’—the pooled chord family mean vectors —learned in the PCP ROT train18system.While it is dif?cult to make any strong inter-pretation of this plot,it is interesting to see the similarities and differences between the different chords.3.4Output Example
Figure 2shows an eight-second segment of the song “Eight Days a Week”taken about 16seconds into the song.The display consists of the PCP feature vectors shown in a spectrogram-like format.Underneath are three sets of chord labels:the hand-marked ground truth,the labels obtained by forced alignment,and the labels returned by recognition (using the PCP ROT/train18system).While this is only a small fragment,it gives a ?avor of the nature of the results obtained.
4Future Work
4.1Training Parameters
Our future work on this system will concentrate on the follow-ing areas:
X
I
R
T
A
M
N
O
I S
U
F
N
O
C
"
R
O
J
A
M
A
"
k e e
W
a
s y a
D
t h g i E
j a
M n i
M7j a
M7n i
M7
m
o
D g u
A m i D A4.71..94..
b
B/#
A.......
b
C/B.......
C/#
B.......
b
D/#
C.......
D.3.....
b E/#
D.......
b F/E715..1..
F/#E1......
b
G/#F.9.....
G.......
b
A/#
G.......
X
I
R
T
A
M
N
O
I S
U
F
N
O
C
"
R
O
N
I
M
B
"
k e e
W
a
s y a
D
t h g i E
j a
M n i
M7j a
M7n i
M7
m
o
D g u
A m i D
b
C/B.27.....
C/#
B.......
b
D/#
C.......
D.3.....
b E/#
D.......
b F/E815.14...
F/#E33.....
b
G/#F.21.6... G2......
b
A/#
G.......
A....1..
b
B/#
A.9.....
X
I
R
T
A
M
N
O
I S
U
F
N
O
C
"
R
O
J
A
M
D
"
k e e
W
a
s y a
D
t h g i E
j a
M n i
M7j a
M7n i
M7
m
o
D g u
A m i D
D03911.594..
b E/#
D.......
b F/E8143.14...
F/#E7......
b
G/#F.24.51...
G.......
b
A/#
G.......
A916..67..
b
B/#
A...25...
b
C/B.02.....
C/#
B.......
b
D/#
C.1.....
X
I
R
T
A
M
N
O
I S
U
F
N
O
C
"
R
O
J
A
M
E
"
k e e
W
a
s y a
D
t h g i E
j a
M n i
M7j a
M7n i
M7
m
o
D g u
A m i D
b F/E851511.9...
F/#E9......
b
G/#F...11...
G3......
b
A/#
G.......
A9...1..
b
B/#
A.......
b
C/B8...,..
C/#
B.......
b
D/#
C.02.....
D.41.....
b E/#
D.......
X
I
R
T
A
M
N
O
I S
U
F
N
O
C
"
R
O
J
A
M
G
"
k e e
W
a
s y a
D
t h g i E
j a
M n i
M7j a
M7n i
M7
m
o
D g u
A m i D
G22153.....
b
A/#
G.......
A11......
b
B/#
A.......
b
C/B.42.3...
C/#
B.......
b
D/#
C.......
D3171.21..
b E/#
D.......
b F/E1401.62...
F/#E.......
b
G/#F.21.....
X
I
R
T
A
M
N
O
I S
U
F
N
O
C
"
D
R
O
H
C
X
"
k e e
W
a
s y a
D
t h g i E
j a
M n i
M7j a
M7n i
M7
m
o
D g u
A m i D
A91......
b
B/#
A.......
b
C/B.12.....
C/#
B.......
b
D/#
C.......
D.53.....
b E/#
D.......
b F/E.......
F/#E.......
b
G/#F.1.....
G.......
b
A/#
G.......
Table4:Confusion matrices for recognition of“Eight Days a Week”,PCP ROT,train18.Enharmonic equivalent chords have been combined.
?More data and parameters:In section3.1,we noted that the PCP ROT chord family models show no signs of over?tting,so employing more parameters,e.g.by us-ing Gaussian mixture models rather than single Gaussians, should achieve further accuracy improvements.Of course,
a larger and more diverse collection of training data should
also improve accuracy and applicability of the system.The most signi?cant obstacle to obtaining this data is?nding a reliable source for the associated chord sequences.
?Frequency Resolution:As observed from the ma-jor/minor chord confusion,our recognition system most likely does not have enough frequency resolution.A sim-ple remedy is to use longer FFT windows;increasing the Hanning length to8192may allow the system better to dis-tinguish neighboring notes.This issue is particularly seri-ous at low frequencies,when the spacing of adjacent FFT bins becomes greater than one quarter-tone.Currently we assign all energy in these low bins to a single chroma,but better results might be obtained by spreading it across sev-eral PCP dimensions in proportion to their overlap with the FFT bin frequency range.
?Adaptive Tuning:One argument for using24-dimensional PCP vectors was to accommodate slight vari-ations in tuning.Another way to help ensure that notes do not adversely interact with the PCP bin edges would be to estimate the precise tuning used in a particular song, and center the PCP feature de?nition accordingly.This can be accomplished by performing a much?ner FFT on long portions of the original?le,determining the most intense frequency and its corresponding pitch,and then shifting the FFT to PCP mapping such that this frequency falls pre-cisely in the middle of a note.
?Different Features:We chose PCP features because of their prior success in chord classi?cation tasks,but we are also interested in very different kinds of features.One idea we would like to try is looking at the autocorrelation of subband energy envelopes at the very long lags that emerge as the least common multiple of the different fundamental frequencies making up a chord.
5Conclusion
Our experiments show that HMM models trained by EM on PCP features can successfully recognize chords in unstructured, polyphonic,multi-timbre audio.This is a challenging instance of extracting complex musical information from a complex in-put signal has many practical applications,since harmonic in-formation covers much of the character of western music.Be-cause our system uses only the raw audio.it should be applica-ble over a wide range of circumstances.
Although recognition accuracy is not yet suf?cient to provide usable chord transcriptions of unknown audio,the ability to?nd time alignments for known chord progressions may be useful in itself.Moreover,the minimally-supervised EM training ap-proach means that the incorporation of large amounts of addi-tional training data should be straightforward,since no manual annotation is required.A larger system of this kind should result in much more precise and successful models.Acknowledgments
Our thanks go to the anonymous reviewers for their helpful comments.
References
Bartsch,M.A.and Wake?eld,G.H.(2001).To catch a chorus: Using chroma-based representations for audio thumbnailing.In Proc.IEEE Workshop on Applications of Signal Processing to Audio and Acoustics,Mohonk,New York.
Fujishima,T.(1999).Realtime chord recognition of musical sound:A system using common lisp music.In Proc.ICMC, pages464–467,Beijing.
Gold,B.and Morgan,N.(1999).Speech and Audio Signal Pro-cessing:Processing and Perception of Speech and Music.John Wiley&Sons,Inc.
Logan,B.(2000).Mel frequency cepstral coef?cients for music mode ling.In Proc.Int.Symposium on Music Inform.Retriev. (ISMIR),Plymouth.
Paperback Song Series:The Beatles(1995).Hal Leonard Cor-poration.
Raphael,C.(2002).Automatic transcription of piano music.In Proc.Int.Symposium on Music Inform.Retriev.(ISMIR),Paris. Young,S.,Odell,J.,Ollason,D.,Valtchev,V.,and Woodland,P. (1997).HTK Hidden Markov Model Toolkit.Entropic Research Laboratories Inc.,Cambridge University.
数据结构课程设计计算器
数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式
对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / %
4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map —107— Ca-Chord ：基于主从环的Chord 路由算法 李京文1,2，熊 焰1，高 燕1,2 (1. 中国科学技术大学计算机科学技术系，合肥 230026；2. 安徽职业技术学院，合肥 230051) 摘 要：提出基于主从结构的Chord 路由算法。该算法根据区域组成多个子环，在子环中推选出处理能力强的节点为超节点彼此相连构成主环。每次路由都从子环开始，然后进入主环，确定路由跳节点后，再在该节点对应的子环查找目标节点，使得大部分路由都在子环执行，避免在整个P2P 环上往复跨区域查找，减少路由跳数，提高路由延时性能。 关键词：主从Chord ；超节点；分布式哈希表 Ca-Chord: Chord Routing Algorithm Based on Main and Subordinate Ring LI Jing-wen 1,2, XIONG Yan 1 , GAO Yan 1,2 (1. Department of Computer Science and Technology, University of Science and Technology of China, Heifei 230026; 2. Anhui V ocational and Technical College, Heifei 230051) 【Abstract 】This paper proposes the Chord routing algorithm based on the main and subordinate structure. The algorithm composes many subrings according to the region. The super node is elected according to the node’s handling abilities in the subring, and each of super nodes constitutes the main ring and connects each other. Each time the routing starts from subring, and then enters the main ring. After the routing jump node is definited, the goal node is searched in the subring to correspond this node. The majority of routing executes in the subring so that the search on the entire P2P ring which moves in the cross region back and forth is avoided and the jump numbers are reduced. The algorithm greatly enhances the routing delay performance. 【Key words 】main and subordinate Chord; super node; distributed Hash table 计 算 机 工 程 Computer Engineering 第35卷 第11期 ol.35 No.11 2009年6月 June 2009 网络与通信· 文章编号：1000—3428(2009)11—0107—03 文献标识码：A 中图分类号：TP303 V ·1 概述 P2P 技术以其去中心点、可扩展、实时性、可靠性、负 载均衡等优点使其在很多领域都有广泛的应用前景。由于Chord 协议的简单性和在大量节点的动态加入与离开情况下，其稳定算法也能维持良好查询效率，这个优点使得目前许多研究项目都建立在Chord 协议之上，但是Chord 完全没有考虑节点的拓扑特性，因此，在大型P2P 网络中，2个Peer 之间的延迟变化很大，很可能出现一个路由跳发生在2个延迟很大的节点间，这也容易造成信息长距离的传递而使网络拥塞。为了降低Chord 的查询延时，提高查询效率，本文提出基于主从环的超节点Chord ，改善Chord 路由性能，降低网络流量。 2 相关研究工作 Chord 协议是麻省理工学院的研究小组设计的一种分布式哈希表，它被广泛用于DNS, P2P 等分布式网络环境中。Chord 协议将中心索引服务器分散化，要求每个节点存储部分路由信息，并在Chord 环内执行路由转发过程。因此，路由表的尺寸成为影响性能的关键指标。如果这个值设置过大，虽然降低了转发跳数，但是节点加入和退出的随意性很容易导致路由表频繁变更；而该值过小，又会造成网络直径的增大，降低数据查询的效率。对于Chord 来说，路由表的尺寸与网络直径都等于lb N 。 研究人员对于Chord 有很多的研究，并且也在试图对其进行一些改进。文献[1]对Chord 协议进行一个真实环境的测试，提到了Chord 协议在文件分布、查找和负载均衡等方面 的一些实测结果。miChord [2]扩展了Chord 的网络拓扑，使得一些节点能够组织为一个组，然后在Chord 协议的基础上，建立层次结构的网络环境，而且miChord 对组的通信是建立在应用层组播的基础上的，这样虽然理论上提高查找的效率，但是其开销却特别的大。文献[3]利用数论方法，使得路由表的长度与网络直径降低21.4%，但是平均路径长度却增加了22.7%。文献[4]则提出利用Chord 换的双向特性并研究标识符表示位的取值，以此提高路由性能。 本文在Chord 基础上提出一种Ca-Chord 模型，在该模型中，对超节点设置Chord 主环，其他节点按照物理拓扑设置为从Chord 环，从环内的节点实现自治，从环间的查询和路由通过超节点进行，从而降低查询延时，提高查询效率，降低网络流量。 3 Ca-Chord 模型 Ca-Chord 模型建立在Chord 基础上，将超节点和多环的思想引入Chord 环内，实现从环自治。本节重点描述超节点的产生、主环的组成、从环的结构以及路由原理等。 3.1 Ca-Chord 的体系结构 (1)超级节点及作用 在P2P 系统中，用户可以达到数以万计，其中存在很大一部分的拨号上网用户和性能很差的PC 机用户，这些节点 作者简介：李京文(1965－)，女，副教授，主研方向：计算机网络；熊 焰，教授、博士后、博士生导师；高 燕，副教授 收稿日期：2008-12-20 E-mail ：Lijingwen7135@https://www.wendangku.net/doc/5c17706002.html, 万方数据 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件方面从功能考虑，首先选择内部存储资源丰富的AT89C51单片机，输入采用4×4矩阵键盘。显示采用3位7段共阴极LED动态显示。软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C 语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C51芯片、汇编语言、数码管、加减乘除 目录 摘要 (01) 引言 (01) 一、设计任务和要求............................. 1、1 设计要求 1、2 性能指标 1、3 设计方案的确定 二、单片机简要原理............................. 2、1 AT89C51的介绍 2、2 单片机最小系统 2、3 七段共阳极数码管 三、硬件设计................................... 3、1 键盘电路的设计 3、2 显示电路的设计 四、软件设计................................... 4、1 系统设计 4、2 显示电路的设计 五、调试与仿真................................. 5、1 Keil C51单片机软件开发系统 5、2 proteus的操作 六、心得体会.................................... 参考文献......................................... 附录1 系统硬件电路图............................ 附录2 程序清单.................................. 微机课程设计报告 题目简易计算器仿真 学院（部）信息学院 专业通信工程 班级2011240401 学生姓名张静 学号33 12 月14 日至12 月27 日共2 周 指导教师（签字）吴向东宋蓓蓓 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C52芯片、汇编语言、数码管、加减乘除 电子琴和弦表 下面我们用C大调来举例。 基本和弦共7个:C,Dm,Em,F,G,Am,Bdim. CDEFGAB就是(1234567) 大三和弦是大三度加小三度(C D E F G A B) 小三和弦是小三度加大三度(Cm Dm Em Fm Gm Am Bm Gm) C-1-3-5 Cm-#-5 Cb7 C7和弦就C加一个7度音bB的换句话说就是C 和弦的5(G)加一个小三度的音bB(#A) 依次类推 以c调为例c调下的多指和弦:C_135 C(9)-1235 C6-1356 C6(9)-12356 CM7-1357 CM7(9)-12357 CM7(#11)-123#457 C(b5)-13#4 CM7b5-13#47 Csus4-145 Caug-13#5 CM7aug-13#57 Cm-1#25 Cm(9)-12#25 Cm7-1#25#6 Cm7(9)-12#25#6 Cm7(11)-12#245#6 CmM7-1#257 CmM7b5-1#2#37 CmM7(9)-12#257 Cm7b5-1#2#3#6 Cdim-1#2#3 Cdim7-1#2#36 C7-135#6 C7(b9)-1#135#6 C7(b13)-135#5#6 C7(9)-1235#6 C7(#11)-123#45#6 C7(#9)1#235#6 C7(13)-1356#6 C7b5-13#4#6 C7aug-13#5#6 C7sus4145#6 C1+2+5-125下面针对和弦的简单构成发表一下我的讲解： 三和弦分为大三和弦，小三和弦，增三和弦和减三和弦 具体说： 1、2、3、4、5、6、7、1、这7个音中3-4、7-1之间是半音关系 其他的都是全音关系 大三和弦：135 1、3之间是两个全音 3-5之间是一个全音和一个半音 象这样的三个音成为大三和弦 再吉他中用大写字母表示 小三和弦：246 2-4之间是一个全音和一个半音 4-6之间是两个全音 象这样的三个音成为小三和弦 增三和弦：13#5 1-3之间是两个全音 3-#5之间也是两个全音 象这样的三个音成为增三和弦 减三和弦：724 7-2之间是一个全音和一个半音 2-4之间也是一个全音和一个半音 象这样的三个音成为减三和弦 和声效果： 大三和弦具有明亮、坚定的效果 小三和弦具有阴暗、柔和的效果 安卓应用程序设计 ——简易计算器的实现院（系）名称 专业名称 学生姓名 学生学号 课程名称 2016年6月日 1.系统需求分析 Android是以Linux为核心的手机操作平台，作为一款开放式的操作系统，随着Android 的快速发展，如今已允许开发者使用多种编程语言来开发Android应用程序，而不再是以前只能使用Java开发Android应用程序的单一局面，因而受到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通过算法实行简单的数学计算从而提高了数学计算的效率，实现计算器的界面优化，使界面更加友好，操作更加方便。基于android的计算器的设计,系统具有良好的界面；必要的交互信息；简约美观的效果。使用人员能快捷简单地进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际要求，系统应实现以下功能：计算器界面友好，方便使用，，具有基本的加、减、乘、除功能，能够判断用户输入运算数是否正确，支持小数运算，具有清除功能。 图2.1系统功能图 整个程序基于Android技术开发，除总体模块外主要分为输入模块、显示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的键盘输入以及 响应触屏的按键，需要监听手机动作以及用指针事件处理方法处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以及最终的计算结 VB应用程序的设计方法 ——“简易计算器”教学设计 揭阳第一中学卢嘉圳 教学内容：利用所学知识制作Visual Basic程序“简易计算器” 教学目标：能熟练运用CommandButton控件及TextBox控件进行Visual Basic(以下简称VB)程序的设计，能熟练运用条件语句编写代码 教学重点:运用开发VB程序一般过程的思路来开发“简易计算器” 教学难点:分析得出实现“简易计算器”各运算功能的算法。 教材分析： 当我刚开始进行程序设计的教学时，便感觉比较难教。这是因为程序设计本身枯燥、严谨，较难理解，而且学生大多数都是初学者，没有相应的知识基础。对于《程序设计实例》，我们选用的教材是广东教育出版社出版的《信息技术》第四册，该书采用的程序设计语言是VB，而学生是仅学过了一点点简单的QB编程之后就进入《程序设计实例》的学习的。 教材为我们总结了设计VB程序的一般步骤：创建用户界面；设置控件属性；编写事件程序代码；运行应用程序。我总结了一下，其实VB程序设计可分为设计用户界面及编写程序代码两个环节。 教学过程： 一、引入新课 任务：让学生按照书上提示完成一个非常简单的VB程序——“计算器”（仅包含开方、平方、求绝对值功能）的制作。 目的：加强对CommandButton控件及TextBox控件的掌握，复习对开方、求绝对值函数的使用。 引入本节课的学习任务：设计一个简易计算器，包含加、减、乘、除、开方、平方等运算。程序界面可参考下图。 具体功能为：在Text1中输入一个数值，然后单击代表运算符的按钮则运算结果会在text2中显示出来；比如在text1中输入一个2，然后按“+”按钮，再输入一个3按“-”按钮，再输入一个-4按“*”按钮，则实际为(2-3)*(-4)；最后在text2中显示结果为4。 升号是#，降号是b,都写在音符前面,高音符号是g,低音符号是d C C:1 3 5 Cm:1 b3 5 C7:1 3 5 b7 Caug(C+):1 3 #5 Cdim(C°):1 b3 b5 6 C6:1 3 5 6 Cm6:1 b3 5 6 C9:1 2 3 5 Cm9:1 2 b3 5 Cm7:1 b3 5 b7 Cmaj7:1 3 5 7 alt C7(C7-5):1 3 b5 7 C#=Db C#(Db):#1 4(#3) #5 C#m(Dbm):#1 3 #5 C#7(Db7):#1 4(#3) #5 7 C#aug(C#+)Dbaug(Db+):#1 4(#3) 6 C#dim(C#°)Dbdim(Db°):#1 3 5 b7 C#6(Db6):#1 4(#3) #5 #6 C#m6(Dbm6):#1 3 #5 #6 C#9(Db9):#1 #2 4(#3) #5 C#m9(Dbm9):#1 #2 3 #5 C#m7(Dbm7):#1 3 #5 7 C#maj7(Dbmaj7):#1 4 #5 1(g). altC#m7(C#m7-5)altDbm7(Dbm7-5):#1 4 5 D D:2 #4 6 Dm:2 4 6 D7:2 #4 6 1(g) Daug(D+):2 #4 #6 Ddim(D°):2 4 b6 7 D6:2 #4 6 7 Dm6:2 4 6 7 D9:2 3 #4 6 Dm9:2 3 4 6 Dm7:2 4 6 1(g) Dmaj7:2 #4 6 #1(g) alt D7(D7-5):2 #4 b6 1(g) Eb=D# Eb(D#):b3 5 b7 Ebm(D#m):b3 b5 b7 Eb7(D#7):b3 5 b7 b2(g) Ebaug(Eb+)D#aug(D#+):b3 5 7 Ebdim(Eb°)D#dim(D#°):b3 b5 6 b7 Eb6(D#6):b3 5 b7 1(g) Ebm6(D#):b3 b5 b7 1(g) Eb9(D#6):b3 4 5 b7 Ebm9(D#m9):b3 4 b5 b7 Ebm7(D#m7):b3 b5 b7 b2(g) alt Eb7(Eb7-5)altD#7(D#7-5):b3 5 6 b2(g) E E:3 #5 7 Em:3 5 7 E7:3 #5 7 2(g) Eaug(E+):3 #5 1(g) Edim(E°):3 5 b7 #1(g) E6:3 #5 7 #1(g) Em6:3 5 7 #1(g) E9:3 #4 #5 7 Em9:3 #4 5 7 Em7:3 5 7 2(g) Emaj7:3 #5 7 #2(g) altE7(E7-5):3 #5 b7 2(g) F F:4 6 1(g) Fm:4 b6 1(g) F7:4 6 1(g) b3(g) Faug(F+):4 6 #1(g) Fdim(F°):4 b6 7 2(g) F6:4 6 1(g) 2(g) Fm6:4 b6 1(g) 2(g) F9:4 5 6 1(g) Fm9:4 5 b6 1(g) Fm7:4 b6 1(g) b3(g) Fmaj7:4 6 1(g) 3(g) altF7(F7-5)altGb7(Gb7-5):4 6 b1(g)(7) b3(g) G G:5 7 2(g) Gm:5 b7 2(g) G7:5 7 2(g) 4(g) Gaug(G+):5 7 #2(g) Gdim(G°):5 b7 b2 3 G6:5 7 2(g) 3(g) Gm6:5 b7 2(g) 3(g) G9:5 6 7 2(g) Gm9:5 6 b7 2(g) Gm7:5 b7 2(g) 4(g) Gmaj7:5 7 2 #4 altG7(G7-5):5 7 b2(g) 4(g) Ab=G# Ab(G#):b6 1(g) b3(g) Ab7(G#7):b6 1(g) b3(g) b5(g) Abaug(Ab+)G#aug(G#+):b6 1(g) 3(g) Abdim(Ab°)G#dim(G#°):b6 7 2(g) 4(g) Abm7G#m7:b6 b1(g) b3(g) b5(g) Abmaj7G#maj7:b6 1(g) b3(g) 5(g) altAb7(Ab7-5) altG#7(G#7-5):b6 1(g) 2(g) b6(g) A A:6 #1(g) 3(g) Am:5 1(g) 3(g) A7:5 #1(g) 3(g) 5(g) Aaug(A+):5 #1(g) 4 Adim(A°):6 1(g) b3(g) b5(g) A6:5 #1(g) 3(g) #4(g) Am6:5 1(g) 3(g) #4(g) A9:6 7 #1(g) 3(g) Am9:6 7 1(g) 3(g) Am7:6 1(g) 3(g) 5(g) Amaj7:5 #1(g) 3(g) #5(g) altA7(A7-5):5 #1(g) b3(g) 5(g) Bb=A# Bb(A#):b7(d) 2 4 模拟计算器 学生姓名：**** 指导老师：**** 摘要本课程设计的课题是设计一个模拟计算器的程序，能够进行表达式的计算，并且表达式中可以包含Abs()和Sqrt()运算。在课程设计中，系统开发平台为Windows ，程序设计设计语言采用C++，程序运行平台为Windows 或*nix。本程序的关键就是表达式的分离和处理，在程序设计中，采用了将输入的中缀表达式转化为后缀表达式的方法，具有可靠的运行效率。本程序做到了对输入的表达式（表达式可以包含浮点数并且Abs()和Sqrt()中可以嵌套子表达式）进行判定表达式是否合法并且求出表达式的值的功能。经过一系列的调试运行，程序实现了设计目标，可以正确的处理用户输入的表达式，对海量级数据都能够通过计算机运算快速解决。 关键词C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定； 目录 1 引言 (3) 1.1课程设计目的 (3) 1.2课程设计内容 (3) 2 设计思路与方案 (4) 3 详细实现 (5) 3.1 表达式的合法判定 (5) 3.2 中缀表达式转化为后缀表达式 (5) 3.3 处理后缀表达式 (7) 3.4 表达式嵌套处理 (8) 4 运行环境与结果 (9) 4.1 运行环境 (9) 4.2 运行结果 (9) 5 结束语 (12) 参考文献 (13) 附录1：模拟计算器源程序清单 (14) 1 引言 本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率。 1.1课程设计目的 数据结构主要是研究计算机存储，组织数据，非数值计算程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 模拟计算器程序主要利用了“栈”这种数据结构来把中缀表达式转化为后缀表达式，并且运用了递归的思想来解决Abs()和Sqrt()中嵌套表达式的问题，其中还有一些统计的思想来判定表达式是否合法的算法。 1.2课程设计内容 本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1 用户输入表达式。 2 判定表达式是否合法。 3 把中缀表达式转化为后缀表达式。 4 求出后缀表达式的结果。 5 输出表达式的结果。通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算。 课题：用计算器计算 教学内容：三年级下册第48—51页内容 教学目标： 1、在运算中了解计算器的结构和基本功能；能正确、熟练地运用计算器进行一、两步的式题运算。 2、能运用计算器解决一些简单的实际问题，探索一些基本的数学规律。 3、培养观察、比较、分析、归纳、概括等能力。 教学过程： 一、尝试运用 师：开学到现在，我们一直在学习计算，下面这些题，哪些你一眼能看出来答案的，直接说的得数。 1、初步尝试 90＋56= 45×99≈ 87546—3469= 42×30= 2102÷30≈ 43×365= 师：最后两道看来有困难，列竖式算算。 师：先不报答案，要你自己检验做的对不对，你准备怎么样？试一试用计算器来验算，你们会吗？ 师：谁愿意带上你的竖式计算上来展示意下，向大家演示一下你用计算器验算的过程可以吗？（鼓励和表扬） 师：看来，大家还真的会用计算器！想不想“再显身手”？ 2、再次尝试：探索用计算器进行混合运算的方法 ①546×28－4276 ②2940 ÷28＋763 ③15021-87×99 ④25120÷（449－289） （1）这4题与上面4题相比，有什么不一样？会做吗？请试一试。 （2）交流操作方法。 （3）你有没有感觉到这4道题在计算过程中有什么不一样？ （4）用计算器计算③、④该怎么操作呢？我们以第③题为例，谁来介绍介绍？ （突出“记住中间数”、“使用MR键”、倒减等方法。） （①、②两题只要按顺序依次输入，③、④题要先算后一步，③④可以“记住过程得数”，③还可以倒减等） （5）介绍用存储键计算，尝试用“MR键”计算③④题。 二、解决生活问题 师：通过这几道题计算，你感觉计算器怎么样？你们喜欢用计算器吗？下面我们就发挥计算器的作用，用它来完成一个非常有价值的问题。 1、出示：一个水龙头滴水的动态画面。据统计一个没有关紧的水龙头，每天大约滴18千克的水，这些水就这样白白流掉了。 （1）照这样计算一年(按365天计算)要浪费多少千克水？ （2）把这些水分别装在饮水桶中(每桶约重15千克)算算大约能装多少桶？ （3）你家每月用几桶水？算算这些水够你家用几个月？大约合多少年？ 师：目前我国西南大旱，一些地区粮食因为缺水绝收。云南山区的孩子们喝脏水解渴。联系我们刚才的这些计算数据，你想到什么？ 三、探索计算规律： 师：既然人们发明了这么好的计算器，我们就应该更好地运用它。让我们来挑战一下自己，探索计算的规律好不好？ 1、找出规律后再填写每组的后2题得数，并用计算器检验。 19+9×9= 118+98×9= 1117+987×9= 11116+9876×9= 111115+98765×9= 学生汇报自己的发现。按这样一种规律写下去，下一题该是什么样的？ 2、自己探索规律。 1122÷34= 111222÷334= 11112222÷3334= …… 111…1222…2÷333…34= 2001个1 2001个2 2000个3 2014，50（23）1引言对等网络P2P （Peer to Peer ）是一种分布式网络，它有别于传统的C/S （Client/Server ）网络模式。在P2P 网络中，所有的计算机都以同等地位相连来共享资源，每台计算机既能充当客户端，又能作为服务器向其他计算机提供资源和服务。随着互联网的广泛应用，P2P 技术的应用和服务已经成为人们网络生活中的重要组成部分，如分布式计算、即时通信、文件交换、协同设计等，而承载这些应用的重要机制则是资源的搜索定位技术。根据P2P 网络的拓扑结构，可将P2P 网络资源搜索算法分为3种模式：（1）中央索引模式。利用中心索引服务器存储数据的元数据信息，如Napster [1]等。这种模式缺点是当系统中节点数增多时，中心索引服务器就会 成为系统的瓶颈。（2）采用洪泛的搜索模式。每个节点都储存自身的信息或信息索引，当需要获取信息时，用洪泛的方式进行搜索，如Gnutella [2]等。用该种模式采用洪泛机制发现资源时，容易引起消息的泛滥而且难以扩展。（3）分布式哈希表模式。该模式基于DHT （Distribute Hash Table ）技术，网络中的每个节点只存储特定信息或特定信息的索引，当需要进行资源搜索时，根据节点中的特定信息就可以逐步地找到资源。如chord [3]、CAN [4]、 Pastry [5]和Tapestry [6]等。这种模式避免了洪泛查找，提高了信息搜索的效率。 chord 算法是结构化P2P 网络中基于DHT 技术的一基于新路由表的双向搜索chord 路由算法 王慧，王铮 WANG Hui,WANG Zheng 重庆大学计算机学院，重庆400030 College of Computer Science,Chongqing University,Chongqing 400030,China WANG Hui,WANG Zheng.Bidirectional search chord routing algorithm based on new finger https://www.wendangku.net/doc/5c17706002.html,puter Engi-neering and Applications,2014,50（23）：95-99. Abstract ：A bidirectional search chord routing algorithm based on new finger table is proposed according to the issue of searching resources efficiently in structured P2P network.This algorithm puts forward a new finger table structure formula to solve the problem of overmuch redundancy and low searching efficiency.On the premise of not increasing the finger table ’s item,the new formula proposes routing factor and makes full use of the average distance between nodes in chord ring.The new finger table not only has no redundancy items,but also achieves bidirectional search in chord ring to reduce the average lookup path length.The simulation results show that this algorithm removes the redundancy information,reduces the average lookup path length and gets higher efficiency. Key words ：structured Peer to Peer （P2P ）network;new finger table;bidirectional search chord routing algorithm;routing factor;resources efficient search 摘要：针对结构化P2P （Peer to Peer ）网络资源高效搜索问题，提出了一种基于新路由表的双向搜索chord 路由算法。该算法为解决chord 算法路由表中存在着大量冗余信息，查找资源效率低下等缺点，提出了一个新的路由表构造公式。该公式首次加入路由因子概念，充分考虑了网络中节点个数和资源个数对路由表的影响，在不增加路由表项的前提下，不仅基本删除了路由表的冗余项，还实现了chord 环的双向查找以减少平均查找跳数。实验仿真结果表明，该算法基本消除了路由表中的冗余信息，减少了平均查找跳数，有效地提高了资源的查找效率。 关键词：结构化对等（P2P ）网络；新路由表；双向搜索chord 路由算法；路由因子；资源高效搜索 文献标志码：A 中图分类号：TP393doi ：10.3778/j.issn.1002-8331.1301-0006 作者简介：王慧（1988—），女，硕士研究生，主要研究领域为分布式系统、网络路由算法、网络通信；王铮（1953—），男，副教授，硕 士生导师，主要研究方向为嵌入式操作系统、分布式系统、软件自动生成。E-mail ：tracyh1988@https://www.wendangku.net/doc/5c17706002.html, 收稿日期：2013-01-05修回日期：2013-03-11文章编号：1002-8331（2014）23-0095-05 CNKI 网络优先出版：2013-04-18,https://www.wendangku.net/doc/5c17706002.html,/kcms/detail/11.2127.TP.20130418.1618.017.html Computer Engineering and Applications 计算机工程与应用 95 “移动应用开发”实验报告 1 而受至到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通 过算法实行简单的或学计算从而提高了数学计算的效率，实现计算器的界面 优化，使界面更加友好，操作更加方便。基于android的计算器的设计系统具 有良好的界面；必要的英互信息：简约美观的效票，使用人员能快捷简单地 进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充 分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际需求，系统应实现以下功能：计算器界面友好， 方便使用，具有基本的加，减，乘，除功能。能够判断用户输入运算数是否 正确，支持小数运算，具有清除功能。 整个程序基于Android 技术开发，除总体模块外主要分为输入模块、显 示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之 前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算 以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的 键盘输入以及响应触屏的按键，需要监听手机动作以及用指针事件处理方法 处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以 及最终的计算结果，同时负责显示一些其他的信息。 计算器模块主要描述了计算器的整体，实现了计算器的界面，负责用户 2 输入数据，计算，显示，清零等功能。 2.2输入模块设计 系统如果想完成计算器中各种功能，首先用户要能进行数据输入，由于 是在触屏手机上开发计算器程序，所以要求输入可以直接使用触屏进行，所 以在设计的时候就要充分的考虑这一点。正是由于考虑到这个特殊的地方， 所以在进行模块设计中，选择编写输入模块类的时候会特意选取使用可以支 持触屏输入的特殊增强型图形用户界面类。 输入模块主要的任务是描述计算器键盘以及实现键盘的监听，即当用户 点击按键或者屏幕的时候监听会去调用相应的处理办法，本模块还需要为系 统提供一个较为直观的键盘图形用户界面。输入模块的功能图如图 2.3显示模块设计 作为手机计算器系统，显示部分也是必不可少的一部分。没有显示部分 就没有办法显示用户输入的数字是否正确，甚至不能显示计算出的结果，由 此可见显示模块即包括输入的部分（因个人技术原因不能显示表达式的形式）也包括输出的部分。 显示模块主要完成的任务是描述计算器的显示区，该区域用于显示用户 输入的数据以及最终的计算结果和一些其他信息。同时本模块还将提供调用 和设置显示的具体方法。 3 计算器算法原理 除法也用类似竖式的方法，从高位到低位逐一得出结果。大概过程如下：（注意，是二进制运算） 1、先左移除数，直到除数不小于被除数，同时记录移动的位数； 2、开始循环，循环次数为前一步移动的位数加1； 3、比较被除数与除数的大小，如果被除数不小于除数，则该位结果为1，否则为0； 4、除数右移一位，继续循环。 这种方法同样可以进行小数运算，根据需要的有效数字位数确定循环次数。 漏了一点，修改一下： 3、比较被除数与除数的大小，如果被除数不小于除数，则该位结果为1，并把被除数减去除数，否则为0 加减乘除求余： #include 奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）做了一个调查，投票选出32个最重要的算法： 1.A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一 种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定 次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。 2.集束搜索（又名定向搜索，Beam Search）——最佳优先搜索算法的优化。使用启 发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最 前面的m个最符合条件的节点，m是固定数字——集束的宽度。 3.二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半 不符合要求的数据。 4.分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决 方案的算法，特别是针对离散、组合的最优化。 5.Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几 里得算法和线性系统中高斯消元法的泛化。 6.数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对 信息编码的过程，又叫来源编码。 7.Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况 下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一 起，加密后续通讯。 8.Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。 9.离散微分算法（Discrete differentiation） 10.动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构 算法 11.欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的 算法之一，出现在公元前300前欧几里得的《几何原本》。 12.期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在 统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一 步上求得的最大可能值来计算参数的值。 13.快速傅里叶变换（Fast Fourier transform，FFT）——计算离散的傅里叶变换（DF T）及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。 14.梯度下降（Gradient descent）——一种数学上的最优化算法。 15.哈希算法（Hashing） 16.堆排序（Heaps） 17.Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统 和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。 18.LLL算法（Lenstra-Lenstra-Lovasz lattice reduction）——以格规约（lattice）基数 为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用： 背包加密系统（knapsack）、有特定设置的RSA加密等等。Ca-Chord-基于主从环的Chord路由算法
简易计算器
微机课设简易计算器
电子琴和弦表
基于安卓的计算器的设计与实现
计算器制作
电子琴多指和弦表
模拟计算器程序-课程设计
用计算器计算(教案)
基于新路由表的双向搜索chord路由算法
移动应用开发实验---简单计算器
计算器算法原理
计算机中的常用算法