|
Hello everyone. I am just a beginner programmer.
I am learning recursion and dynamic programming.
I realized that even for Fibonacci numbers, recursion is not suitable - and there you need to use dynamic programming.
:thumbsup:
Well, I looked at the tutorials, it's good when you can deduce the recurrent relation and then everything is clear...
But if we cannot do it, how then?
????
For example, I took the famous task "Knight's tour" and solved it using recursion.
using System;
namespace KnightChess
{
class Field
{
public int index { get; set; }
public Field(int _index)
{
index = _index;
}
}
class Board
{
int height;
int width;
public (int, int) curKnightPos;
int value;
public Field[,] boardArr;
public static bool CanMoveKnight1(Board Board)
{
return (Board.width > Board.curKnightPos.Item1 + 1) && (Board.height > Board.curKnightPos.Item2) &&
(Board.boardArr[Board.curKnightPos.Item1 + 1, Board.curKnightPos.Item2].index == -1);
}
public static Board MoveKnight1(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1 += 2;
Transformed.curKnightPos.Item2++;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight2(Board Board)
{
return (Board.width > Board.curKnightPos.Item1) && (Board.height > Board.curKnightPos.Item2 + 1) &&
(Board.boardArr[Board.curKnightPos.Item1, Board.curKnightPos.Item2 + 1].index == -1);
}
public static Board MoveKnight2(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1++;
Transformed.curKnightPos.Item2 += 2;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight3(Board Board)
{
return (Board.curKnightPos.Item1 > 1) && (Board.height > Board.curKnightPos.Item2 + 1) &&
(Board.boardArr[Board.curKnightPos.Item1 - 2, Board.curKnightPos.Item2 + 1].index == -1);
}
public static Board MoveKnight3(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1--;
Transformed.curKnightPos.Item2 += 2;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight4(Board Board)
{
return (Board.curKnightPos.Item1 > 2) && (Board.height > Board.curKnightPos.Item2) &&
(Board.boardArr[Board.curKnightPos.Item1 - 3, Board.curKnightPos.Item2].index == -1);
}
public static Board MoveKnight4(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1 -= 2;
Transformed.curKnightPos.Item2++;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight5(Board Board)
{
return (Board.curKnightPos.Item1 > 2) && (Board.curKnightPos.Item2 > 1) &&
(Board.boardArr[Board.curKnightPos.Item1 - 3, Board.curKnightPos.Item2 - 2].index == -1);
}
public static Board MoveKnight5(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1 -= 2;
Transformed.curKnightPos.Item2--;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight6(Board Board)
{
return (Board.curKnightPos.Item1 > 1) && (Board.curKnightPos.Item2 > 2) &&
(Board.boardArr[Board.curKnightPos.Item1 - 2, Board.curKnightPos.Item2 - 3].index == -1);
}
public static Board MoveKnight6(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1--;
Transformed.curKnightPos.Item2 -= 2;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight7(Board Board)
{
return (Board.width > Board.curKnightPos.Item1) && (Board.curKnightPos.Item2 > 2) &&
(Board.boardArr[Board.curKnightPos.Item1, Board.curKnightPos.Item2 - 3].index == -1);
}
public static Board MoveKnight7(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1++;
Transformed.curKnightPos.Item2 -= 2;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static bool CanMoveKnight8(Board Board)
{
return (Board.width > Board.curKnightPos.Item1 + 1) && (Board.curKnightPos.Item2 > 1) &&
(Board.boardArr[Board.curKnightPos.Item1 + 1, Board.curKnightPos.Item2 - 2].index == -1);
}
public static Board MoveKnight8(Board Board)
{
Board Transformed = new Board(Board);
Transformed.curKnightPos.Item1 += 2;
Transformed.curKnightPos.Item2--;
Transformed.boardArr[Transformed.curKnightPos.Item1 - 1, Transformed.curKnightPos.Item2 - 1].index = ++Transformed.value;
return Transformed;
}
public static void Print(Board Board)
{
for (int i = Board.width - 1; i >= 0; i--)
{
for (int j = 0; j < Board.height; j++)
{
Console.Write(Board.boardArr[i, j].index + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
public static bool isFull(Board Board)
{
foreach(var el in Board.boardArr)
{
if (el.index == -1)
{
return false;
}
}
return true;
}
public Board(Board Board)
{
height = Board.height;
width = Board.width;
curKnightPos = Board.curKnightPos;
value = Board.value;
boardArr = new Field[width, height];
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
boardArr[i, j] = new Field(Board.boardArr[i, j].index);
}
}
}
public Board(int _height, int _width, (int, int) _curKnightPos)
{
height = _height;
width = _width;
curKnightPos = _curKnightPos;
value = 1;
boardArr = new Field[_width, _height];
for(int i = 0; i < _width; i++)
{
for (int j = 0; j < _height; j++)
{
boardArr[i, j] = new Field(-1);
}
}
boardArr[_curKnightPos.Item1 - 1, _curKnightPos.Item2 - 1].index = 1;
}
}
class Program
{
static void Main(string[] args)
{
#region input and define
Console.WriteLine("Please enter board's width");
string temp;
temp = Console.ReadLine();
int width;
bool success;
success = int.TryParse(temp, out width);
if (!success)
{
Console.WriteLine("Width be natural a number");
return;
}
Console.WriteLine("Please enter board's height");
temp = Console.ReadLine();
int height;
success = int.TryParse(temp, out height);
if (!success)
{
Console.WriteLine("Height be natural a number");
return;
}
Console.WriteLine("Please enter board's curKnightPosX");
temp = Console.ReadLine();
int curKnightPosX;
success = int.TryParse(temp, out curKnightPosX);
if (!success)
{
Console.WriteLine("CurKnightPosX be natural a number");
return;
}
Console.WriteLine("Please enter board's curKnightPosY");
temp = Console.ReadLine();
int curKnightPosY;
success = int.TryParse(temp, out curKnightPosY);
if (!success)
{
Console.WriteLine("CurKnightPosY be natural a number");
return;
}
if ((curKnightPosX > width) || (curKnightPosY > height))
{
Console.WriteLine("curKnightPos out of range");
return;
}
Board Board = new Board(height, width, (curKnightPosX, curKnightPosY));
#endregion
GetTransformsMap(Board);
Console.ReadKey();
}
private static void GetTransformsMap(Board board)
{
if (!Board.CanMoveKnight1(board) && !Board.CanMoveKnight2(board) && !Board.CanMoveKnight3(board) && !Board.CanMoveKnight4(board) &&
!Board.CanMoveKnight5(board) && !Board.CanMoveKnight6(board) && !Board.CanMoveKnight7(board) && !Board.CanMoveKnight8(board))
{
if (Board.isFull(board))
{
Board.Print(board);
}
}
if (Board.CanMoveKnight1(board))
{
GetTransformsMap(Board.MoveKnight1(board));
}
if (Board.CanMoveKnight2(board))
{
GetTransformsMap(Board.MoveKnight2(board));
}
if (Board.CanMoveKnight3(board))
{
GetTransformsMap(Board.MoveKnight3(board));
}
if (Board.CanMoveKnight4(board))
{
GetTransformsMap(Board.MoveKnight4(board));
}
if (Board.CanMoveKnight5(board))
{
GetTransformsMap(Board.MoveKnight5(board));
}
if (Board.CanMoveKnight6(board))
{
GetTransformsMap(Board.MoveKnight6(board));
}
if (Board.CanMoveKnight7(board))
{
GetTransformsMap(Board.MoveKnight7(board));
}
if (Board.CanMoveKnight8(board))
{
GetTransformsMap(Board.MoveKnight8(board));
}
}
}
}
We enter the size of the board and the coordinates of the initial position of the knight - after which the calculation takes place.
Video attached
DropMeFiles – free one-click file sharing service[^]
As you can see from the video for 8x8, we get one of the solutions in a reasonable amount of time.
But if the task is to get all the solutions?
Even for 6x6 it already freezes - everything depends on memory, I have 8GB of RAM.
:) :) :)
Help, how can this example be optimized to get ALL solutions?
Will it change anything if rewritten in C ++ or there in python?
|
|
|
|
|
I'm not getting it: How could anyone even consider doing the Fibonacci sequence recursively? For printing it backwards?
|
|
|
|
|
You really surprised me. I watched a lot of tutorials - on recursion and almost everyone has an example with Fibonacci
static int fib(int n, int a , int b )
{
if (n == 0)
return a;
if (n == 1)
return b;
return fib(n - 1, b, a + b);
}
|
|
|
|
|
Kari Trust wrote: I watched a lot of tutorials - on recursion and almost everyone has an example with Fibonacci
I can see a single reason for using fibonacci to illustrate recursion: To show that it isn't needed. The keyword is tail recursion.
Certainly, a good compiler will detect tail recursion and save stack space and call overhead, generating a simple jump to the top of the function (after fixing up the parameter block, of course), changing the recursion to an iteration. You might as well do that yourself  ... unless, of course, you are so deeply into recursive thinking that you find it hard to consider fibonacci anything but recursive. (I can imagine mathematicians that are that way, but not many programmers!
To me, the obvious way to write a fibonacci-function would be (I consider the sequence to start with 0, labeled the 0th fibonacci number - some people argue details):
static int fib(int n) {
if (n < 2) return n;
int prev = 1;
int fibn = 1;
for (int iteration = 2; iteration < n; iteration++) {
int fibnext = fibn + prev;
prev = fibn;
fibn = fibnext;
}
return fibn;
}
Bonus sidetrack (or is it?):
If you want to make sure that you master recursion, terminating conditions in particular, try this little exercise: Make a console program with recursive function that for each call writes an output line on the console of RecursionDepth number of spaces, followed by an asterisk (and a newline).
If the main program calls this function with arguments NumberOfTeeth, BladeWidth, ToothLength, the output should look like a sawblade; the recursion goes to the maximum recursion depth, ToothLength. Then it returns to BladeWidth recursion depth, before it again recurses to ToothLength depth a second time, and repeats this for at total of NumberOfTeeth dives into the maximum depth, before finally returning to the main program.
If you are a seasoned recursioner, maybe you will find this problem trivial (in that case, forward it to your students or junior programmers!) I have never ever seen anyone getting this perfectly right on the first try, though! Most programmers give it a first try, then they curse before making the first correction, then they re-curse before making a second correction, ... The cursing often goes to the maximum depth of re-cursing before they get it right
modified 2-Mar-21 15:00pm.
|
|
|
|
|
I tested my application in an another computer. Sometimes when I hit username/password to enter the main menu, it crashes. I run it again and there is no problem. Sometimes when I change input language in order to type inside a Textbox, it crashes. I used Windows Event to find the reason. I have used an analog clock and an special Font inside my application.
Application: DataGridView.exe
Framework Version: v4.0.30319
Description: The process was terminated due to an unhandled exception.
Exception Info: System.AccessViolationException
at System.Drawing.SafeNativeMethods+Gdip.GdipDrawString(System.Runtime.InteropServices.HandleRef, System.String, Int32, System.Runtime.InteropServices.HandleRef, System.Drawing.Internal.GPRECTF ByRef, System.Runtime.InteropServices.HandleRef, System.Runtime.InteropServices.HandleRef)
at System.Drawing.Graphics.DrawString(System.String, System.Drawing.Font, System.Drawing.Brush, System.Drawing.RectangleF, System.Drawing.StringFormat)
at System.Windows.Forms.Label.OnPaint(System.Windows.Forms.PaintEventArgs)
at System.Windows.Forms.Control.PaintWithErrorHandling(System.Windows.Forms.PaintEventArgs, Int16)
at System.Windows.Forms.Control.WmPaint(System.Windows.Forms.Message ByRef)
at System.Windows.Forms.Control.WndProc(System.Windows.Forms.Message ByRef)
at System.Windows.Forms.Label.WndProc(System.Windows.Forms.Message ByRef)
at System.Windows.Forms.Control+ControlNativeWindow.OnMessage(System.Windows.Forms.Message ByRef)
at System.Windows.Forms.Control+ControlNativeWindow.WndProc(System.Windows.Forms.Message ByRef)
at System.Windows.Forms.NativeWindow.Callback(IntPtr, Int32, IntPtr, IntPtr)
Faulting application name: DataGridView.exe, version: 1.0.0.0, time stamp: 0xc2801969
Faulting module name: gdiplus.dll, version: 10.0.19041.789, time stamp: 0x198e190d
Exception code: 0xc000041d
Fault offset: 0x00030ec9
Faulting process id: 0x980
Faulting application start time: 0x01d70ce394d6e863
Faulting application path: D:\Softwares\PMinfo\DataGridView.exe
Faulting module path: C:\WINDOWS\WinSxS\x86_microsoft.windows.gdiplus_6595b64144ccf1df_1.1.19041.789_none_429ddec08a8f10c1\gdiplus.dll
Report Id: 25065017-745c-4f6b-8d20-a6d15ce398b1
Faulting package full name:
Faulting package-relative application ID:
modified 27-Feb-21 5:02am.
|
|
|
|
|
It might be helpful if you define "analog clock" more clearly. Are you using an over-ridden Paint event in your app ?
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
I didn't make it by myself (I have a tutorial about it) and for shortage of time, I used a dll reference and its corresponding component. I cannot see its code.
I used a special font which does not exist in Windows by default.
|
|
|
|
|
Alex, you've got to stop blindly using code you don't understand, and spend some time learning how it works, and what exactly it does.
You are wasting your time just throwing things at random into your app and hoping for the best - that isn't a viable development strategy!
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Read the error message - it gives you a lot of information.
Exception Info: System.AccessViolationException That's not too specific, so you need further information.
So look firsther, and you get a stack trace: it starts with the code that generated the exception, and then goes back up through the call list.
And it's something to do with painting in a label:
at System.Windows.Forms.Label.OnPaint(System.Windows.Forms.PaintEventArgs)
So the most likely culprit is your "special Font", which we can't see.
Start by replacing your font with a "normal" one and see if the problem goes away. If it does, then something you are drawing either doesn't exist in the font, or is badly "described" leading to a major crash.
So add logging to the app to find out what exactly is being shown when it fails, and try that exact text on your dev computer to see if you can track down exactly what is causing the problem.
Sorry, but we can't do any of that for you!
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Thanks, I tested it. I need to use a better font. The font I used cannot be used through IDE properties. So, I tried to put my font in reference and use code for displaying it.
For solving my problem, I copied my special font to windows font and the problem solved.
|
|
|
|
|
Hi,
I have used several TextBoxes and ComboBoxes in my own project. I want to reset TextBoxes at once by pressing a button. I wrote a simple method as follows:
foreach (var c in Controls)
{
if (c is TextBox)
{
((TextBox)c).Clear();
}
}
When I run the code, nothing happens. 
All TextBoxes have their own existing texts.
Please guide me.
modified 26-Feb-21 12:14pm.
|
|
|
|
|
The docs say nothing about "Clear" doing anything "visible".
I'd use:
if ( c is TextBox tb ){
tb.Text = "";
}
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Clear works in both WinForms and WPF.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Never used it. Can't think of a reason either ... particularly since I want the TB to reflect what's in the binding target, and vise versa. I have no idea what Clear does in this case.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
That will work - on textboxes, it won't touch ComboBoxes - provided they aren't inside any containers: Panel, Splitters, GroupBoxes, and so on. If they are, then you need to recurse though the container.Controls collection as well in order to find them.
It will also only find TextBoxes which are in the current instance of a Form - ones in a different Form or a different instance will not be found and cleared.
But in more recent versions of C#, it's clearer to do this than cast:
private void MyButton_Click(object sender, EventArgs e)
{
foreach (Control c in Controls)
{
if (c is TextBox tb)
{
tb.Clear();
}
}
}
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
It doesn't still make any effect. Finally, I found the issue. I have put those Textboxes in a GroupBox. When the TextBoxes are out of the GroupBox, the code works, but inside the GroupBox it fails.
How can I solve it?
modified 26-Feb-21 1:27am.
|
|
|
|
|
You need a recursive method that can take a Control as a parameter, clear all the textboxes in that control, then go through all the container controls, calling itself, passing in each one those controls.
|
|
|
|
|
I refer the honorable gentleman to my original reply:
Quote: provided they aren't inside any containers: Panel, Splitters, GroupBoxes, and so on. If they are, then you need to recurse though the container.Controls collection as well in order to find them.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
OriginalGriff wrote: I refer the honorable gentleman to my original reply
Wow.
And this not the first time, you seem very patient and kind 
Bastard Programmer from Hell 
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
See my reply on using 'GetType<> below. Call the method on YourGroupBox.Controls ... or any other ContainerControl [^]
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
Normally the answer to your issue is still given ...
Perhaps additional :
What you have to do is :
- iterate throught the Controls-collection of your Form
- if the type of the control is a Textbox then do your work
- if not look if the control has entries in it's own controls-Collection
- if Yes : do the same again - please realize : your can also have a Panel inside a Panel inside a Panel ...
- also : realize that most of the controls could be also ContainerControls with controls in it
Why do the controls inside a Panel (or a GroupBox or a TabView or ...) not directly belong to the Form ? It is because there a some functions of the ConatinerControl which direct effect the cointrols in it - for example : Visible, Enable ...
But what you also can do is :
Create your own customized Control (derive it from the Control which matches most to your issue) and implement the function you need to it - for example : clear all Textboxes inside it ...
|
|
|
|
|
You can use 'OfType<> to select only cerain types of Controls:
foreach (var tb in this.Controls.OfType<TextBox>())
{
tb.Clear();
}
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
Wow! Thanks for that, Bill. Good timing.
Yesterday evening I had written
bool found = false;
foreach (object obj in URIsMenu.Items)
if (obj is ToolStripMenuItem)
{
ToolStripMenuItem item = (ToolStripMenuItem)obj;
item.Checked = item.Text == SelectedItem;
if (item.Checked)
found = true;
}
Your useful reply has shortened that to
bool found = false;
foreach (ToolStripMenuItem item in URIsMenu.Items.OfType<ToolStripItem>())
{
item.Checked = item.Text == SelectedItem;
found |= item.Checked;
}
|
|
|
|
|
I was composing a reply to a QA question today [^], and I started thinking about why I made the following assumptions in C#:
1) app scoped global variables are evil
2) defining a static class outside my own/any NameSpace is evil.
Given the strongly-typed/OOP gestalt of C#, why did its designers allow something like this:
public static class Constants
{
public const double PI = Math.PI;
public static double E { set; get; } = Math.E;
}
namespace WhatEver
{}Opinions ?
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
It doesn't have to be a static class, any class can be defined outside all namespaces, in which case it's part of the default namespace: namespace keyword - C# Reference | Microsoft Docs[^]
Quote: Whether or not you explicitly declare a namespace in a C# source file, the compiler adds a default namespace. This unnamed namespace, sometimes referred to as the global namespace, is present in every file. Any identifier in the global namespace is available for use in a named namespace.
Why? You'd probably have to ask the language authors ...
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
