Facebook
Google
GitHub
Linkedin
find repeated number
- Thread starter Gajyamadake
- Start date
I referenced that thread in post #9.
I have seen that but I am trying to understand logic on paper first. Can anyone help me with the flow chart where I'm struggling
Now you need to examine your toy problem and look for the underlying patterns.
Why do you have five blocks of statements?
What would change if you had a list with twelve numbers in it?
What does each block of statements have in common?
What is different from one block to the next?
In my opinion, you are trying to go for too much eloquence given your current understanding of how to develop algorithms. Don't worry about efficiency at all, at least not yet. Look for the simplest method that will produce the correct result and figure out how to convert that from a toy problem to a flow chart to a program. Then go back and look for ways to improve efficiency.
In this case, it appears that an unstated part of the problem is that the list contains exactly one value that is repeated. Is that really a part of the problem specification? If not, what should happen if more than one number is repeated? What should happen if a number is repeated more than once? What should happen if no numbers are repeated?
Let's press forward with the assumption that the list contains exactly one number that is repeated.
How might a young child go about tackling this problem, assuming you constrained them in a way that was comparable to the constraints that a computer program has (i.e., it can't look from afar at the entire contents of the array, but rather can only look at one or two elements at a time).
How about something like: For each number in the list, count how many times that number appears in the list. If it appears more than once, it is the repeated number and you are done, if it only appears once, continue with the next number.
Can you turn that into pseudocode or a flow chart.
I certainly went with the sort first approach. In the back of my mind I wondered if there was some more elegant method, since a sort does use CPU time if the array is huge. I figured that the time a programmer spends avoiding a sort would be more than the time the computer spends just doing it.
I’d be very curious to speedtest algorithms to see if sorting first is the winning strategy or whether another approach wins.
Sorting requires accessing all of the data at least once. Then another pass would be required to access the sorted data. An algorithm that visits each element once will be faster.
There are a number of compromise approaches.
You could do a partial sort and then check each of the sublists.
For instance, take your list and put each item into one of 16 lists depending on the value of the last four bits (of course, you could put it into one of 256 lists depending on the last byte or whatever works best in terms of memory availability).
Then you can go across each of those lists and if it contains one or fewer numbers, you can skip the list entirely. If it has two or more than you could either do a brute force search just in that list, or you could parse that list into another 16 lists based on the next-to-least four bits. It would be easy to parameterize this so that lists less than a certain length get brute force search and longer ones get parsed further.
But there really is no point trying get fancy until you are capable to doing it simple. Otherwise you lose sight of the forest for the trees.
Roger that. The context of the other thread was whatever you could come up with in a job interview. My opinion is that code that works for most cases would be the minimal acceptable answer. Ten percent of a “perfect” solution might impress the right person but would be a very risky strategy in an interview.
Assuming this is self-edification, not homework per se, here's a way to consider that doesn't involve sorting.
1) You need to define the array size and have a way to enter each value.
2) Clear a block of registers equal to the array size
3) Set indirect addressing to the start of that block (e.g., FSR1)
4) Use each value in the array as a pointer/offset to the FSR
5) Does that register have a marker?*
Here's some sample code to illustrate those steps. I just set bit(7) as the marker. Of course,that limits the size of the array. The actual testing for a duplicate begins at line #53. In brief, this uses FSR offsets to sort without actually moving the values to those registers. No problem with moving the value to the register either, see edit.*
Tested in simulation only.
*Edit: Marker can be anything. One could move the value using XOR and check for zero to see if the register is occupied. That might be more amenable to larger numbers, say 16-bit. Of course, most things will have limitations. XOR'ing will potentially have a problem with zero, Setting a bit met the TS's question and allowed an easy and fast bit test.
1) You need to define the array size and have a way to enter each value.
2) Clear a block of registers equal to the array size
3) Set indirect addressing to the start of that block (e.g., FSR1)
4) Use each value in the array as a pointer/offset to the FSR
5) Does that register have a marker?*
If no = add the marker
If yes = you have found the duplicate, stop
Here's some sample code to illustrate those steps. I just set bit(7) as the marker. Of course,that limits the size of the array. The actual testing for a duplicate begins at line #53. In brief, this uses FSR offsets to sort without actually moving the values to those registers. No problem with moving the value to the register either, see edit.*
Code:
;*******************************************************************************
list p=16f1829 ; list directive to define processor
#include <p16f1829.inc> ; processor specific variable definitions
errorlevel -302, -305
list st=off
RADIX dec
;*******************************************************************************
__CONFIG _CONFIG1, _FOSC_INTOSC & _WDTE_OFF & _PWRTE_OFF & _MCLRE_ON & _CP_OFF & _BOREN_OFF & _CLKOUTEN_OFF & _IESO_OFF & _FCMEN_OFF
;__0x09E4
__CONFIG _CONFIG2, _WRT_OFF & _PLLEN_ON & _STVREN_OFF & _BORV_19 & _LVP_OFF
;__0x1DFF
CBLOCK 0x20
answer
ENDC
#define RAMoffset 0x2A ;0x20 + 10
#define ArraySize 10
#define RAMend 52 ;CBLOCK start + RAMoffset + Array Size
org 0x00
bra Start
Start
ClearRAM
movlw RAMoffset ;begining GPR register |B0
movwf FSR1 ; |B0
RAMloop
clrf INDF1 ; |B0
incf FSR1,f ; |B0
movlw RAMend ;ending GPR register |B0
xorwf FSR1,w ; |B0
btfss STATUS,2 ; |B0
bra RAMloop ; |B0
movlw RAMoffset
movwf FSR1
Array2Test ;6,4,2,1,3,1
movlw 6
call Loop
movlw 4
call Loop
movlw 2
call Loop
movlw 3 ;1 Various numbers tested here
call Loop
movlw 3
call Loop
movlw 1
call Loop
;add safety net for end in case no duplicates
NOP
Test4Dup
Loop ;enter with value in WREG
addwf FSR1,f
btfsc INDF1,7
bra Duplicate
bsf INDF1,7
subwf FSR1,f
return
Duplicate
movwf answer
nop ;light LED or other signal
bra $-1
END*Edit: Marker can be anything. One could move the value using XOR and check for zero to see if the register is occupied. That might be more amenable to larger numbers, say 16-bit. Of course, most things will have limitations. XOR'ing will potentially have a problem with zero, Setting a bit met the TS's question and allowed an easy and fast bit test.
Last edited:
I think I have chosen a difficult path which is very difficult to walk. Where do i start to find the repeated numbers. How to set small tasks to achieve this big problem.
Can you manually show the calculation how human know the repeated number on paper. I mean calculation not flow chart and pseudocode so that I can try to make flow chart for handy calculation
Humans are good at recognizing patterns, as are some other species, including monkeys, who might actually be better than us. So for the problem you show, most humans would solve it by inspection, I think.
If the series were much bigger, I would probably either order the array and search for duplicates or search for 2 or more numbers at a time, crossing off those that failed.
BobaMosfet
- Joined Jul 1, 2009
- 2,211
Stop. Of course you do. How would you do it in your head? Copy that process in your flowchart. Your mind keeps track of a number and counts how many times it's seen that number.... seems like you can repeat that process in your flow chart maybe perhaps using another array....
Beyond that, reading books like this will help you
Title: Algorithms in C, 3rd Ed. [Parts 1-4, Fundamentals, Data Structures, Sorting, Searching]
Author: Robert Sedgewick
ISBN: 0-201-31452-5
If you can follow the logic of the flowchart I posted, it should be straightforward to write the code.
Let's start with the most basic step of processing a list of numbers -- walking across the list and doing something.
Assume that the prior code populated an array called 'data[]' and stored the size of data into a variable called sizeOfData.
So, just for example, we might have
int data[] = {5, 3, 7, 1, 6, 3, 9, 12 , 21, 13, 16};
int sizeOfData = 11;
Can you write the code to walk across the data and do nothing more than just print out each number on a separate line?
Here is my code
C:
#include <stdio.h>
int main()
{
int data[11] = {5, 3, 7, 1, 6, 3, 9, 12 , 21, 13, 16};
for ( int sizeOfData = 0; sizeOfData <11; sizeOfData++)
printf( "data = %d \n", data[ sizeOfData]);
return 0;
}data = 3
data = 7
data = 1
data = 6
data = 3
data = 9
data = 12
data = 21
data = 13
data = 16
This is an interesting problem and one that emphasizes the importance of employing a proper problem solving strategy in the first place.
As I have always maintained, writing code is the last thing you want to do. You need to arrive at an algorithm or strategy first. Then you can draw a flowchart. Pseudocode serves the same purpose as a flowchart. You may create either or both as an exercise.
If the range of numbers and the size of the array are low then sorting the array is the first strategy that comes to mind. However, if the size of the array is very large then sorting is very inefficient.
The solution I would choose is one called hashing which is a technique used to create a table of variable names by a code compiler. This is very similar to how dictionary searches are performed.
Let us as, an example, suppose that there are 1000 numbers to be searched. The range of each number can be unlimited. For simplicity we shall assume that the range of numbers be limited to 16-bit unsigned integers, i.e. 0 to 65535. If we choose to include negative values then the range is -32768 to 32767.
If there are 1000 numbers and there turns out to be no duplicates, then there will be 1000 unique numbers, regardless of values. If there are duplicates then there will be fewer than 1000 unique numbers. Hence our hash table does not have to be greater than 1000 entries. The way a hash function works, it will attempt to compress 65536 possible values into a table with only 1000 entries. Evidently, two different values will encode to the same table entry. The hash function has a way to resolve this. Therefore, let us make the hash table 20% larger, i.e. the table will have 1200 entries.
How does the hash function work?
You take the first number, for example, 12345.
You create any mathematical function that reduces this 16-bit value to say a 10-bit value (0-1023 possible answers). This 10-bit result is the index into the hash table. You enter the value 12345 into the hash table and mark this entry as being occupied. (There is a reason for doing this).
You take the next number and repeat the above process for all numbers in the input array. This process is very efficient compared to sorting. Inevitably you will encounter a clash where an entry in the hash table is already filled with a different number. (Of course, if it is already filled with the same number, you simply update the occurrence count.) The hash function finds a new storage location for the incoming value. In the entry of the previous value you record a link to the new storage location. In this way a thread is maintained of all values that hashed to the same table entry,
There you have it.
In order to draw a flowchart of this algorithm, break it up into separate tasks. For example, draw the flowchart of a hash function.
As I have always maintained, writing code is the last thing you want to do. You need to arrive at an algorithm or strategy first. Then you can draw a flowchart. Pseudocode serves the same purpose as a flowchart. You may create either or both as an exercise.
If the range of numbers and the size of the array are low then sorting the array is the first strategy that comes to mind. However, if the size of the array is very large then sorting is very inefficient.
The solution I would choose is one called hashing which is a technique used to create a table of variable names by a code compiler. This is very similar to how dictionary searches are performed.
Let us as, an example, suppose that there are 1000 numbers to be searched. The range of each number can be unlimited. For simplicity we shall assume that the range of numbers be limited to 16-bit unsigned integers, i.e. 0 to 65535. If we choose to include negative values then the range is -32768 to 32767.
If there are 1000 numbers and there turns out to be no duplicates, then there will be 1000 unique numbers, regardless of values. If there are duplicates then there will be fewer than 1000 unique numbers. Hence our hash table does not have to be greater than 1000 entries. The way a hash function works, it will attempt to compress 65536 possible values into a table with only 1000 entries. Evidently, two different values will encode to the same table entry. The hash function has a way to resolve this. Therefore, let us make the hash table 20% larger, i.e. the table will have 1200 entries.
How does the hash function work?
You take the first number, for example, 12345.
You create any mathematical function that reduces this 16-bit value to say a 10-bit value (0-1023 possible answers). This 10-bit result is the index into the hash table. You enter the value 12345 into the hash table and mark this entry as being occupied. (There is a reason for doing this).
You take the next number and repeat the above process for all numbers in the input array. This process is very efficient compared to sorting. Inevitably you will encounter a clash where an entry in the hash table is already filled with a different number. (Of course, if it is already filled with the same number, you simply update the occurrence count.) The hash function finds a new storage location for the incoming value. In the entry of the previous value you record a link to the new storage location. In this way a thread is maintained of all values that hashed to the same table entry,
There you have it.
In order to draw a flowchart of this algorithm, break it up into separate tasks. For example, draw the flowchart of a hash function.
most of people suggest advice to solve problem with paper and pencil. I have tried my best attempt to solve problem if possible can someone show me how do you solve the problem with paper and pencil?
Granted. Paper and pencil is a useful visual aid.
I solve problems in my head first before applying it to paper.
For example, I thought myself how to swim in my head while lying in bed.
Similarly, I thought myself to play my first two-handed piano piece "Greensleeves" by imagining my fingers in my head.
